参考：http://blog.csdn.net/vmurder/article/details/44542575
和2337有点像
设点u的经过期望(还是概率啊我也分不清，以下都分不清）为( x[u] ) ，度为 ( in[u] )，边( (u,v) ) 的经过期望为 ( frac{x[u]}{in[u]}+frac{x[v]}{in[v]} )
那么转换为求每个点的经过期望，( x[u]=sum_{v}^{vsubset son(u)}frac{x[v]}{in[v]} )
高斯消元即可。
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
const int N=505,M=250005;
using namespace std;
int n,m;
int U[M],V[M],d[N];
double a[N][N],x[N],w[M],ans;
void Gauss(int n,int m)
{
for(int i=1;i<m;i++)
{
int k=i;
for(int j=i+1;j<=n;j++)
if(fabs(a[k][i])<fabs(a[j][i]))
k=j;
if(i!=k)
for(int j=i;j<=m;j++)
swap(a[i][j],a[k][j]);
for(int j=i+1;j<=n;j++)
{
double rate=a[j][i]/a[i][i];
for(k=i;k<=m;k++)
a[j][k]-=a[i][k]*rate;
}
}
for(int i=m-1;i;i--)
{
for(int j=i+1;j<m;j++)
a[i][m]-=a[i][j]*x[j];
x[i]=a[i][m]/a[i][i];
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&U[i],&V[i]);
d[U[i]]++,d[V[i]]++;
}
for(int i=1;i<n;i++)
a[i][i]=-1;
for(int i=1;i<=m;i++)
{
a[U[i]][V[i]]+=1.0/d[V[i]];
a[V[i]][U[i]]+=1.0/d[U[i]];
}
for(int i=1;i<=n;i++)
a[n][i]=0;
a[1][n+1]=-1,a[n][n]=1;
Gauss(n,n+1);
for(int i=1;i<=m;i++)
w[i]=x[U[i]]/d[U[i]]+x[V[i]]/d[V[i]];
sort(w+1,w+m+1);
for(int i=1;i<=m;i++)
ans+=(m-i+1)*w[i];
printf("%.3lf
",ans);
return 0;
}