对每一个点设f[i]为期望从i出发的次数（第一次从1出发不算），那么有：f[n]=0；f[1]-1=Σf[x]（(x,i)为一条边）；f[x]=Σf[y]（x≠1,(x,y)为一条边）。
然后解出方程，那么得到一条边的期望经过次数，按期望经过次数从大到小一次赋为1~m即可。
AC代码如下：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdlib>
#define eps 1e-10
#define N 505
using namespace std;
int n,m,d[N];
struct edg{ int x,y; double z; }e[N*N]; double a[N][N];
void solve(){
int i,j,k; double t;
for (i=1; i<=n; i++){
for (j=i; j<=n; j++) if (fabs(a[j][i])>eps) break;
if (j>n) continue; if (j!=i) swap(a[i],a[j]);
for (j=i+1; j<=n; j++) if (fabs(a[j][i])>eps){
t=a[j][i]/a[i][i];
for (k=i; k<=n+1; k++) a[j][k]-=t*a[i][k];
}
}
for (i=n; i; i--){
for (j=i+1; j<=n; j++) a[i][n+1]-=a[i][j]*a[j][n+1];
a[i][n+1]/=a[i][i];
}
}
bool cmp(edg u,edg v){ return u.z>v.z; }
int main(){
scanf("%d%d",&n,&m); int i;
for (i=1; i<=m; i++){
scanf("%d%d",&e[i].x,&e[i].y);
d[e[i].x]++; d[e[i].y]++;
}
for (i=1; i<=m; i++){
a[e[i].x][e[i].y]+=1.0/d[e[i].y];
a[e[i].y][e[i].x]+=1.0/d[e[i].x];
}
for (i=1; i<=n; i++) a[n][i]=0;
for (i=1; i<=n; i++) a[i][i]=-1;
a[1][n+1]=-1;
solve();
for (i=1; i<=m; i++)
e[i].z=a[e[i].x][n+1]/d[e[i].x]+a[e[i].y][n+1]/d[e[i].y];
sort(e+1,e+m+1,cmp);
double ans=0;
for (i=1; i<=m; i++) ans+=e[i].z*i;
printf("%.3f\n",ans);
return 0;
}
by lych
2016.4.6