题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3143
显然如果一条边期望被走过的次数越多，我们就应该给它的编号越小。
所以问题变为如何求每一条边被经过的期望次数。
考虑直接求边的期望有点困难。
设：${g[i]}$表示经过第$i$条边的期望次数，${f[i]}$表示经过第$i$个点的期望次数，${du[i]}$表示第$i$个点的度数。
对于一条边$i$,假设这条边的两段的点分别为${x,y}$,则${g[i]=\frac{f[x]}{du[x]}*\frac{f[y]}{du[y]}}$
所以问题变为如何求每一个点被经过的期望次数
设$e[x][y]$表示点$x,y$之间有连边。这就很裸了，${f[i]=\sum (\frac{f[x]}{du[x]}\left [ e[i][x]=1 \right ] )}$，其中$n$号点只能走进去而不能出来，所以忽略不管，$1$号点应当强制$+1$(因为一开始就从$1$号点开始)
这样就得到了一个$n-1$个未知数和$n-1$个式子的方程组，高斯消元求得每个未知数的解(即${f[i]}$)，然后求出${g[i]}$，然后从大到小排序。
$${\sum _{i=1}^{m}g[i]*i}$$
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<cmath>
#include<cstring>
using namespace std;
#define maxn 510
#define llg long long
#define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
llg n,m;
double a[maxn][maxn],du[maxn],f[maxn],g[maxn*maxn]; struct Edge{llg x,y;}e[maxn*maxn]; bool cmp(double x,double y){return x>y;} void guass()
{
llg r;
for (llg i=;i<=n;i++)
{
r=i;
for (llg j=i+;j<=n;j++) if (fabs(a[j][i])>fabs(a[r][i])) r=j;
if (r!=i) for (llg j=;j<=n+;j++) swap(a[r][j],a[i][j]); for (llg k=i+;k<=n;k++)
{
double F=a[k][i]/a[i][i];
for (llg j=i;j<=n+;j++) a[k][j]-=F*a[i][j];
}
} for (llg i=n;i>=;i--)
{
for (llg j=i+;j<=n;j++) a[i][n+]-=f[j]*a[i][j];
f[i]=a[i][n+]/a[i][i];
}
} void init()
{
llg x,y;
cin>>n>>m;
for (llg i=;i<=m;i++)
{
scanf("%lld%lld",&e[i].x,&e[i].y);
du[e[i].x]++,du[e[i].y]++;
}
for (llg i=;i<=m;i++)
{
x=e[i].x,y=e[i].y;
if (y!=n) {a[x][y]=1.00/du[y];}
if (x!=n) {a[y][x]=1.00/du[x];}
}
for (llg i=;i<n;i++) a[i][i]=-;
a[][n]=-;
n--;
} int main()
{
yyj("walk");
init();
guass();
for (llg i=;i<=m;i++) g[i]=f[e[i].x]/du[e[i].x]+f[e[i].y]/du[e[i].y];
double ans=;
sort(g+,g+m+,cmp);
for (llg i=;i<=m;i++) ans+=(double)i*g[i];
printf("%.3lf",ans);
return ;
}