[文章目录]
Description
一个无向连通图，顶点从1编号到N，边从1编号到M。小Z在该图上进行随机游走，初始时小Z在1号顶点，每一步小Z以相等的概率随机选 择当前顶点的某条边，沿着这条边走到下一个顶点，获得等于这条边的编号的分数。当小Z 到达N号顶点时游走结束，总分为所有获得的分数之和。现在，请你对这M条边进行编号，使得小Z获得的总分的期望值最小。
等价于求每条边的经过期望次数，从小到大排序标号，统计贡献即为答案。
等价于求每个点的期望经过次数，设为f[x]，每个点的度数设为d[x]
那么可以得到一堆方程式：f[x]=f[to1]/d[to1]+f[to2]/d[to2]+...f[tom]/do[tom]
f[1]=1+...
f[n]=1
高斯消元即可。
对于double的高斯消元，由于有精度问题，每次要找当前位置最大的一个进行消元。
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 510
int n,m,d[510],a[N*N],b[N*N];
double f[510][510],g[N*N];
int head[N],to[N*N],nxt[N*N],cnt;
inline void add(int x,int y)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt;
}
int main()
{
scanf("%d%d",&n,&m);
int i,j;
for(i=1;i<=m;++i)
{
scanf("%d%d",a+i,b+i);
add(a[i],b[i]); add(b[i],a[i]);
d[a[i]]++; d[b[i]]++;
}
for(i=1;i<=n;++i)
{
f[i][i]=1;
for(j=head[i];j;j=nxt[j]) f[i][to[j]]=-1.0/d[to[j]];
}
for(i=1;i<=n;++i) f[i][n]=f[n][i]=0;
f[1][n+1]=f[n][n+1]=f[n][n]=1;
int k; double t;
for(i=1;i<=n;++i)
{
t=fabs(f[i][i]); k=i;
for(j=i+1;j<=n;++j) if(fabs(f[j][i])>t) t=f[j][i],k=j;
for(j=i;j<=n+1;++j) swap(f[i][j],f[k][j]);
for(k=n+1;k>=i;--k) f[i][k]/=f[i][i];
for(j=1;j<=n;++j) if(j!=i)
{
t=f[j][i];
for(k=i;k<=n+1;++k) f[j][k]-=t*f[i][k];
}
}
for(i=1;i<=m;++i)
{
if(a[i]!=n) g[i]+=f[a[i]][n+1]/d[a[i]];
if(b[i]!=n) g[i]+=f[b[i]][n+1]/d[b[i]];
}
sort(g+1,g+m+1);
for(t=0,i=1;i<=m;++i) t+=g[i]*(m-i+1);
printf("%.3lf",t);
return 0;
}