题目描述

一个无向连通图，顶点从1编号到N，边从1编号到M。
小Z在该图上进行随机游走，初始时小Z在1号顶点，每一步小Z以相等的概率随机选 择当前顶点的某条边，沿着这条边走到下一个顶点，获得等于这条边的编号的分数。当小Z 到达N号顶点时游走结束，总分为所有获得的分数之和。
现在，请你对这M条边进行编号，使得小Z获得的总分的期望值最小。

样例

input
3 3 
2 3
1 2
1 3

output
3.333

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const double eps=1e-7;
struct edge
{
    int to,next;
}e[500001];
int st[500001],n,m,tot,x,y,s[500001],ed[500001];
double d[501],f[501][501],ans[501],sum,ee[500001];
void add(int x,int y)
{
    e[++tot].to=y;
    e[tot].next=st[x];
    st[x]=tot;
}
int dcmp(double x)
{
    if(x<=eps&&x>=-eps)return 0;
    return (x>0)?1:-1;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y;
        add(x,y);
        add(y,x);
        d[x]+=1.0,d[y]+=1.0;
        s[i]=x,ed[i]=y;
    }
    for(int i=1;i<n;i++)
    {
        f[i][i]=1.0;
        for(int j=st[i];j;j=e[j].next)if(e[j].to!=n)f[i][e[j].to]=-1/d[e[j].to];
    }
    f[1][n]=1;
    for(int i=1;i<n;i++)
    {
        int num=i;
        for(int j=i+1;j<n;j++)if(dcmp(f[j][i]-f[num][i])>0)num=j;
        if(num!=i)for(int j=1;j<n+1;j++)swap(f[i][j],f[num][j]);
        for(int j=i+1;j<n;j++)
        {
            if(dcmp(f[j][i]))
            {
                double t=f[j][i]/f[i][i];
                for(int k=1;k<n+1;k++)f[j][k]-=t*f[i][k];
            }
        } 
    }
    for(int i=n-1;i>=1;i--)
    {
        for(int j=i+1;j<n;j++)f[i][n]-=f[i][j]*ans[j];
        ans[i]=f[i][n]/f[i][i];
    }
    for(int i=1;i<=m;i++)ee[i]=ans[s[i]]/d[s[i]]+ans[ed[i]]/d[ed[i]];
    sort(ee+1,ee+m+1);
    for(int i=1;i<=m;i++)sum+=ee[i]*(m-i+1.0);
    printf("%.3lf\n",sum);
}