题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3143
我们令$P_i$表示从第i号点出发的期望次数。则$P_n$显然为$0$。
对于$P_2~P_{n-1}$，则有$P_i= \sum \frac{P_j} {d_j}$，其中节点j与节点i有边相连，$d_j$表示节点j的度数。
对于$P_1$，则有$P_i=1+ \sum \frac{P_j} {d_j}$。
不难发现其实就是一个$n$元一次方程组，我们可以通过高斯消元求出每一个$P_i$。
对于一条边$(x,y)$，经过这条边的期望次数为$ \frac {P_x} {d_x} + \frac {P_y} {d_y}$，我们设此值为$p_i$ 。
我们把期望经过次数从大到小排序，则答案为$\sum_{i=1}^{n} p_i \times i$。
然后就做完了。
AC代码如下：
#include<bits/stdc++.h>
#define M 505
using namespace std;
int a[M][M]={},n,m;
double f[M][M]={},p[M]={},du[M]={}; void solve(){
for(int i=;i<=n;i++){
for(int j=i+;j<=n;j++){
double x=f[j][i]/f[i][i];
for(int k=i;k<=n+;k++)
f[j][k]-=x*f[i][k];
}
}
for(int i=n;i;i--){
for(int j=i+;j<=n;j++)
f[i][n+]-=f[i][j]*p[j];
p[i]=f[i][n+]/f[i][i];
}
}
int X[M*M]={},Y[M*M]={}; double hh[M*M]={};
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++){
int x,y; scanf("%d%d",&x,&y);
a[x][y]=a[y][x]=;
du[x]++; du[y]++;
X[i]=x; Y[i]=y;
}
f[][n+]=-; f[n][n]=;
for(int i=;i<n;i++){
f[i][i]=-;
for(int j=;j<=n;j++) if(a[i][j])
f[i][j]=/du[j];
}
solve();
for(int i=;i<=m;i++)
hh[i]=p[X[i]]/du[X[i]]+p[Y[i]]/du[Y[i]];
sort(hh+,hh+m+);
double ans=;
for(int i=;i<=m;i++)
ans+=hh[i]*(m-i+);
printf("%.3lf\n",ans);
}