【题目描述】
一个无向连通图，顶点从1编号到N，边从1编号到M。
小Z在该图上进行随机游走，初始时小Z在1号顶点，每一步小Z以相等的概率随机选 择当前顶点的某条边，沿着这条边走到下一个顶点，获得等于这条边的编号的分数。当小Z 到达N号顶点时游走结束，总分为所有获得的分数之和。
现在，请你对这M条边进行编号，使得小Z获得的总分的期望值最小。
【输入格式】
第一行是正整数N和M，分别表示该图的顶点数 和边数，接下来M行每行是整数u，v(1≤u,v≤N)，表示顶点u与顶点v之间存在一条边。 输入保证30%的数据满足N≤10，100%的数据满足2≤N≤500且是一个无向简单连通图。
【输出格式】
仅包含一个实数，表示最小的期望值，保留3位小数。
【样例输入】
3 3
2 3
1 2
1 3
【样例输出】
3.333
【提示】
边(1,2)编号为1，边(1,3)编号2，边(2,3)编号为3。
【题解】
对答案贡献大的边编号越小越好，贡献小的边编号自然需要较大，这样想明显需要求出各边经过次数的期望。
首先删去终点的出边，对于每一条边，设其两个节点为u和v：可能从u走到v，也可能从v走到u，从u走到v的期望次数等于经过点u的次数/u的度数，问题转化成求每个点的期望经过次数。
和臭气弹类似地，对于起点,一开始经过一次,也可能从其他点走过来。这是n个变量n个方程的方程组，高斯消元解方程组。
f[1]=1+sigma(f[j]/degree(j),j和1有边)
f[i]=sigma(f[j]/degree(j),j和i有边，i>=2)
求出各边期望的经过次数之后从大到小sort一下，把它的编号作为边权，计算结果即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int sj=;
const double je=1e-;
int n,m,a1,a2,e,h[sj],q[sj*sj],z[sj*sj];
double cd[sj],a[sj][sj],c[sj],jg,xx[sj*sj];
struct B
{
int ne,v;
}b[sj*sj*];
void add(int x,int y)
{
b[e].v=y;
b[e].ne=h[x];
h[x]=e++;
cd[x]++;
}
void init()
{
scanf("%d%d",&n,&m);
memset(h,-,sizeof(h));
for(int i=;i<=m;i++)
{
scanf("%d%d",&a1,&a2);
q[i]=a1;
z[i]=a2;
if(a1!=n) add(a1,a2);
if(a2!=n) add(a2,a1);
}
for(int i=;i<n;i++)
{
a[i][i]=;
for(int j=h[i];j!=-;j=b[j].ne)
a[b[j].v][i]-=/cd[i];
}
c[]=;
a[n][n]=;
}
void jh(double &x,double &y)
{
double temp=y;
y=x;
x=temp;
}
void gs()
{
int zd;
double temp;
for(int i=;i<=n;i++)
{
zd=i;
temp=fabs(a[i][i]);
for(int j=i+;j<=n;j++)
if(temp<fabs(a[j][i]))
{
zd=j;
temp=fabs(a[j][i]);
}
if(zd!=i)
{
for(int j=;j<=n;j++)
jh(a[i][j],a[zd][j]);
jh(c[i],c[zd]);
}
if(fabs(a[i][i])<je) continue;
temp=a[i][i];
for(int j=;j<=n;j++)
a[i][j]/=temp;
c[i]/=temp;
for(int j=;j<=n;j++)
if(i!=j)
{
temp=a[j][i];
for(int k=;k<=n;k++)
a[j][k]-=a[i][k]*temp;
c[j]-=c[i]*temp;
}
}
}
int main()
{
//freopen("t.txt","r",stdin);
freopen("walk.in","r",stdin);
freopen("walk.out","w",stdout);
init();
gs();
for(int i=;i<=m;i++)
{
if(cd[q[i]])
xx[i]+=c[q[i]]/cd[q[i]];
if(cd[z[i]])
xx[i]+=c[z[i]]/cd[z[i]];
}
sort(xx+,xx+m+,greater<double>());
for(int i=;i<=m;i++)
jg+=xx[i]*i;
printf("%.3lf",jg);
//while(1);
return ;
}