题目
题目描述
一个无向连通图，顶点从1编号到N，边从1编号到M。 小Z在该图上进行随机游走，初始时小Z在1号顶点，每一步小Z以相等的概率随机选 择当前顶点的某条边，沿着这条边走到下一个顶点，获得等于这条边的编号的分数。当小Z 到达N号顶点时游走结束，总分为所有获得的分数之和。 现在，请你对这M条边进行编号，使得小Z获得的总分的期望值最小。
输入输出格式
输入格式：
第一行是正整数N和M，分别表示该图的顶点数 和边数，接下来M行每行是整数u，v(1<=u,v<=N)，表示顶点u与顶点v之间存在一条边。 输入保证30%的数据满足N<=10，100%的数据满足2<=N<=500且是一个无向简单连通图。
输出格式：
仅包含一个实数，表示最小的期望值，保留3位小数。
输入输出样例
输入样例#1：
3 3
2 3
1 2
1 3
输出样例#1：
3.333
说明
边(1,2)编号为1，边(1,3)编号2，边(2,3)编号为3。
题解
$f_i$表示$i$点经过的期望次数，首先能列出方程：$f_i=\sum_{(i,j)\in E}\frac{f_j}{du_j}$
这样就可以用高斯消元搞了，注意$f_n=0$，$f_1$的初始值为$1$
已知每个点的期望可以搞出每条边的期望$E(u,v)=\frac{f_u}{du_u}+\frac{f_v}{du_v}$
贪心填编号，期望大的边编号小
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<cmath>
# include<algorithm>
using namespace std;
const int N=505;
const double fs=1e-7;
struct p{
int x,y,fr;
}c[N*N];
int n,m,num,cnt;
double Ans;
int h[N],du[N];
double _ans[N*N];
double f[N][N];
int read()
{
int x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x;
}
void add(int x,int y)
{
++du[x],++du[y];
c[++num]=(p){h[x],y,x},h[x]=num;
c[++num]=(p){h[y],x,y},h[y]=num;
}
void Gauss()
{
for(int i=1,id;i<=n;++i)
{
id=i;
for(int j=i+1;j<=n;++j)
if(fabs(f[j][i])>fabs(f[id][i])) id=j;
if(fabs(f[id][i])<fs) return;
double A=f[id][i];
for(int j=i;j<=n+1;++j)
swap(f[i][j],f[id][j]),f[i][j]/=A;
for(int j=1;j<=n;++j)
if(i!=j)
{
A=f[j][i];
for(int k=i;k<=n+1;++k)
f[j][k]-=f[i][k]*A;
}
}
}
int main()
{
n=read(),m=read();
for(int i=1;i<=m;++i)
add(read(),read());
for(int i=1;i<n;++i)
{
f[i][i]=1;
for(int j=h[i];j;j=c[j].x)
f[i][c[j].y]=-1/double(du[c[j].y]);
}
f[n][n]=f[1][n+1]=1,Gauss();
for(int i=1;i<=num;i+=2)
_ans[++cnt]=f[c[i].y][n+1]/du[c[i].y]+f[c[i].fr][n+1]/du[c[i].fr];
sort(_ans+1,_ans+1+cnt);
for(int i=1;i<=m;++i)
Ans+=_ans[i]*(m-i+1);
return printf("%.3lf",Ans),0;
}
