一个无向连通图，顶点从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 #include <algorithm> 2 #include <iostream> 3 #include <cstring> 4 #include <cstdio> 5 #include <cmath> 6 using namespace std; 7 const int N=510,M=N*N; 8 int n,m,e[M][2],d[N]; 9 long double A[N][N];10 double ans,w[M],x[N];11 void Guass_Elimination(){12     for(int i=1;i<n;i++){13         int p=i;14         for(int j=i+1;j<n;j++)15             if(fabs(A[p][i])<fabs(A[j][i]))16                 p=j;17         if(p!=i)18             for(int j=1;j<=n;j++)19                 swap(A[i][j],A[p][j]);20         long double tmp=A[i][i];21         for(int j=1;j<=n;j++)22             A[i][j]/=tmp;23         for(int j=1;j<n;j++)24             if(i!=j){25                 tmp=A[j][i];26                 for(int k=1;k<=n;k++)27                     A[j][k]-=tmp*A[i][k];28             }29     }30     for(int i=1;i<n;i++)31         x[i]=A[i][n];32 }33 int main(){34     freopen("walk.in","r",stdin);35     freopen("walk.out","w",stdout);36     scanf("%d%d",&n,&m);37     for(int i=1;i<=m;i++){38         scanf("%d%d",&e[i][0],&e[i][1]);39         d[e[i][0]]+=1;d[e[i][1]]+=1;40     }A[1][n]=1;41     for(int i=1;i<n;i++)A[i][i]=1;42     for(int i=1;i<=m;i++){43         if(e[i][0]==n||e[i][1]==n)continue;44         A[e[i][0]][e[i][1]]+=-1.0/d[e[i][1]];45         A[e[i][1]][e[i][0]]+=-1.0/d[e[i][0]];46     }47     Guass_Elimination();48     for(int i=1;i<=m;i++){49         w[i]+=x[e[i][0]]/d[e[i][0]];50         w[i]+=x[e[i][1]]/d[e[i][1]];51     }52     sort(w+1,w+m+1);53     for(int i=1;i<=m;i++)54         ans+=w[i]*(m-i+1);55     printf("%.3lf\n",ans);    56     return 0;57 }