游走（bzoj 3143）

Description

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

Input

第一行是正整数N和M，分别表示该图的顶点数和边数，接下来M行每行是整数u，v(1≤u,v≤N)，表示顶点u与顶点v之间存在一条边。输入保证30%的数据满足N≤10，100%的数据满足2≤N≤500且是一个无向简单连通图。

Output

仅包含一个实数，表示最小的期望值，保留3位小数。

Sample Input

3 3
2 3
1 2
1 3

Sample Output

3.333

HINT

边(1,2)编号为1，边(1,3)编号2，边(2,3)编号为3。

/*
    设点i的出度为d[i]，期望经过的次数为x[i]，边i的期望经过的次数为f[i]。
    那么可以得到以下式子：
    x[i]=Σx[j]/d[j] (j->i)
    f[i]=Σx[u]/d[u]+x[v]/d[v]
    特别的：x[1]=1+x[j]/d[j] (j->1)
            x[n]=1
    然后高斯消元解出方程，让经过次数多的边拥有小的编号。 
*/
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#define N 510
#define M 250010
#define ld long double
using namespace std;
int u[M],v[M],d[N],n,m;
ld a[N][N],x[N],f[M];
void gauss(){
    for(int i=1;i<=n;i++){
        int id=i;ld maxn=fabs(a[i][i]);
        for(int j=i+1;j<=n;j++) if(fabs(a[j][i])>maxn) id=j,maxn=fabs(a[j][i]);
        if(id!=i) swap(a[id],a[i]);
        ld t=1.0/a[i][i];
        for(int j=1;j<=n+1;j++) a[i][j]*=t;
        for(int j=1;j<=n;j++){
            if(j==i) continue;
            ld t=a[j][i];
            for(int k=i;k<=n+1;k++)
                a[j][k]-=t*a[i][k];
        }
    }
    for(int i=n;i;i--){
        ld tmp=0;
        for(int j=i+1;j<=n;j++)
            tmp+=x[j]*a[i][j];
        x[i]=a[i][n+1]-tmp;
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&u[i],&v[i]);
        d[u[i]]++;d[v[i]]++;
        
    }
    for(int i=1;i<=n;i++) a[i][i]=-1;
    for(int i=1;i<=m;i++){
        if(v[i]!=n) a[u[i]][v[i]]+=1.0/d[v[i]];
        if(u[i]!=n) a[v[i]][u[i]]+=1.0/d[u[i]];
    }
    for(int i=1;i<n;i++) a[n][i]=0;
    for(int i=1;i<=n;i++){
        if(i==1||i==n) a[i][n+1]=-1;
        else a[i][n+1]=0;
    }
    gauss();
    for(int i=1;i<=m;i++){
        if(u[i]!=n) f[i]+=x[u[i]]/d[u[i]];
        if(v[i]!=n) f[i]+=x[v[i]]/d[v[i]];
    }
    sort(f+1,f+m+1);
    ld ans=0;
    for(int i=1;i<=m;i++)
        ans+=f[i]*(m-i+1);
    printf("%.3lf",(double)ans);
    return 0;
}