【题意】给定n个点m条边的无向连通图，每条路径的代价是其编号大小，每个点等概率往周围走，要求给所有边编号，使得从1到n的期望总分最小（求该总分）。n<=500。

【算法】期望+高斯消元

【题解】显然，应使经过次数越多的边编号越小，问题转化为求每条边的期望经过次数。

边数太多，容易知道f(u,v)=f(u)/out(u)+f(v)/out(v)，所以转化为求每个点的期望经过次数，这就是了。

设f[x]表示点x的期望经过次数，根据全期望公式（讨论“经过“的问题不能依赖于下一步）：

$$f[x]=\sum_{y}\frac{f[y]}{out[y]} \ \ , \ \ y \rightarrow x$$

最后f[1]++，f[n]=0。（点1一开始就经过一次，点n不能重新出来，所以设成0不然会影响别的点）

复杂度O(n^3)。

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int maxn=510,M=1000010;//int n,m,out[maxn],u[M],v[M],c[M];double a[maxn][maxn],b[M];void gauss(){    for(int i=1;i
          
           fabs(a[r][i]))r=j;        if(r!=i)for(int j=i;j<=n+1;j++)swap(a[r][j],a[i][j]);        for(int j=i+1;j<=n;j++){            for(int k=n+1;k>=i;k--){                a[j][k]-=a[j][i]/a[i][i]*a[i][k];//            }        }    }    for(int i=n;i>=1;i--){        for(int j=i+1;j<=n;j++)a[i][n+1]-=a[i][j]*a[j][n+1];        a[i][n+1]/=a[i][i];    }}bool cmp(double a,double b){
    return a>b;}int main(){    freopen("input6.txt","r",stdin);    scanf("%d%d",&n,&m);    for(int i=1;i<=m;i++){        scanf("%d%d",&u[i],&v[i]);        a[u[i]][v[i]]++;out[u[i]]++;        if(u[i]!=v[i])a[v[i]][u[i]]++,out[v[i]]++;    }    for(int i=1;i<=n;i++){        for(int j=1;j<=n;j++)if(out[j])a[i][j]/=out[j];        a[i][i]--;    }    a[1][n+1]--;    for(int j=1;j<=n+1;j++)a[n][j]=0;a[n][n]=1;    gauss();    for(int i=1;i<=m;i++)b[i]=a[u[i]][n+1]/out[u[i]]+a[v[i]][n+1]/out[v[i]];    double ans=0;    sort(b+1,b+m+1,cmp);    for(int i=1;i<=m;i++)ans+=b[i]*i;    printf("%.3lf",ans+(1e-13));    return 0;}
          
         
        
       
      

 

注意：边数组比点数组大。