本文版权归ljh2000和博客园共有，欢迎转载，但须保留此声明，并给出原文链接，谢谢合作。
本文作者：ljh2000
作者博客：http://www.cnblogs.com/ljh2000-jump/
转载请注明出处，侵权必究，保留最终解释权！
题目链接：BZOJ3143
正解：高斯消元
解题报告：
因为直接考虑每条边被经过的次数很不好考虑，而对于点统计次数就方便很多了。
令$p[i]$为从$i$出发开始游走的期望次数，则$p[u]=sum{frac{p[v]}{d[v]}},u,v$连通,$d$是点的度数。那么我可以得到一个$n$元$1$次方程组，注意$p[1]=1+sum{frac{p[v]}{d[v]}},1,v$连通,$n$不能走出去,所以无需计算贡献，然后高斯消元解出每个$p$即可。算出$p$之后，一条边的贡献就是所连接的两个点的$p/d$（拆成两个方向的角度很容易想清楚）。我开始想优化精度，就在高斯消元里面加了个$swap$操作发现除以$0$萎掉了…
以后看来不能随便加这种优化了...
//It is made by ljh2000
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <complex>
using namespace std;
typedef long long LL;
typedef long double LB;
typedef complex<double> C;
const double pi = acos(-1);
const int MAXN = 520;
const int MAXM = 250011;
int n,m,d[MAXN];
bool mp[MAXN][MAXN];
LB tot,ans[MAXM],p[MAXN],f[MAXN][MAXN];//p[i]表示从i出发的期望次数
struct edge{ int x,y; }e[MAXM];
inline bool cmp(LB q,LB qq){ return q>qq; }
inline int getint(){
int w=0,q=0; char c=getchar(); while((c<'0'||c>'9') && c!='-') c=getchar();
if(c=='-') q=1,c=getchar(); while (c>='0'&&c<='9') w=w*10+c-'0',c=getchar(); return q?-w:w;
}
inline void gauss(){
LB now;
for(int i=1;i<=n;i++) {
for(int j=i+1;j<=n;j++) {
now=f[j][i]/f[i][i];
for(int l=i;l<=n+1;l++)
f[j][l]-=now*f[i][l];
}
}
for(int i=n;i>=1;i--) {
p[i]=f[i][n+1];
for(int j=i+1;j<=n;j++)
p[i]-=p[j]*f[i][j];
p[i]/=f[i][i];//还需解一个一元一次方程
}
}
inline void work(){
n=getint(); m=getint(); int x,y;
for(int i=1;i<=m;i++) { e[i].x=x=getint(); e[i].y=y=getint(); mp[x][y]=mp[y][x]=1; d[x]++; d[y]++; }
for(int i=1;i<n;i++) {//n走不出去...
for(int j=1;j<=n;j++)
if(mp[i][j])
f[i][j]=1.0/d[j];
f[i][i]=-1;
}
f[1][n+1]=-1;//p[1]=1+sigma(p[v])
f[n][n]=1;
gauss();
for(int i=1;i<=m;i++) ans[i]=p[e[i].x]/d[e[i].x]+p[e[i].y]/d[e[i].y];
sort(ans+1,ans+m+1,cmp);
for(int i=1;i<=m;i++) tot+=ans[i]*i;
printf("%.3Lf",tot);
}
int main()
{
work();
return 0;
}