题目大意：给定一个n个点m条边的无向连通图。在该图上进行随机游走，起点为1号顶点，每一步以相等的概率随机选择当前顶点的某条边，沿着这条边走到下一个顶点，获得等于这条边的编号的分数，到达N号顶点时游走结束，总分为所有获得的分数之和。对这M条边进行编号，使获得的总分的期望值最小。
每条边随意编号，自然是使走得多的边的编号尽量小。问题转为求每条边的期望次数，而边走的次数又是由点转移的，首先要求出每个点的期望经过次数。起点的期望经过次数一定为1，终点的期望经过次数不可能转移到其他点。除了起点和终点，每个点都可能由相邻的点转移过来，所以一个点的期望经过次数f(i)=sigma{j与i有连边 | f(j)*p(j)} ，其中i不等于起点或终点，p(j)代表的是p经过其他的概率，解方程即可。
#include <cstdio> #include <algorithm> #include <cmath> #define N 505 using namespace std; const double eps=1e-10; struct Edge { int u,v; double val; bool operator < (const Edge& rhs) const {return val>rhs.val;} }e[N*N]; int n,m,d[N]; double p[N],a[N][N]; void Gauss() { for(int i=1;i<=n;i++) { int j; for(j=i;j<=n;j++) if(fabs(a[j][i])>eps) break; if(j>n) continue; if(j!=i) for(int k=1;k<=n+1;k++) swap(a[i][k],a[j][k]); for(j=i+1;j<=n;j++) { if(fabs(a[j][i])<eps) continue; double tmp=a[j][i]/a[i][i]; for(int k=i;k<=n+1;k++) a[j][k]-=a[i][k]*tmp; } } for(int i=n;i;i--) { for(int j=i+1;j<=n;j++) a[i][n+1]-=a[i][j]*a[j][n+1]; a[i][n+1]/=a[i][i]; } return ; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { scanf("%d%d",&e[i].u,&e[i].v); d[e[i].u]++, d[e[i].v]++; } for(int i=1;i<=n;i++) p[i]=1.0/(double)d[i]; for(int i=1;i<=m;i++) a[e[i].u][e[i].v]+=p[e[i].v], a[e[i].v][e[i].u]+=p[e[i].u]; for(int i=1;i<=n;i++) a[n][i]=0, a[i][i]=-1; a[1][n+1]=-1; Gauss(); for(int i=1;i<=m;i++) e[i].val=p[e[i].u]*a[e[i].u][n+1]+p[e[i].v]*a[e[i].v][n+1]; sort(e+1,e+1+m); double ans=0; for(int i=1;i<=m;i++) ans+=e[i].val*(double)i; printf("%.3f\n",ans); return 0; }