数学（概率）：HNOI2013 游走

【题目描述】

一个无向连通图，顶点从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.333

【提示】

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

这道题目，先求每个点经过的期望次数，我觉得一般是用正推的，然后贪心。

 #include <algorithm>

 #include <iostream>

 #include <cstring>

 #include <cstdio>

 #include <cmath>

 using namespace std;

 const int N=,M=N*N;

 int n,m,e[M][],d[N];

 long double A[N][N];

 double ans,w[M],x[N];

 void Guass_Elimination(){

     for(int i=;i<n;i++){

         int p=i;

         for(int j=i+;j<n;j++)

             if(fabs(A[p][i])<fabs(A[j][i]))

                 p=j;

         if(p!=i)

             for(int j=;j<=n;j++)

                 swap(A[i][j],A[p][j]);

         long double tmp=A[i][i];

         for(int j=;j<=n;j++)

             A[i][j]/=tmp;

         for(int j=;j<n;j++)

             if(i!=j){

                 tmp=A[j][i];

                 for(int k=;k<=n;k++)

                     A[j][k]-=tmp*A[i][k];

             }

     }

     for(int i=;i<n;i++)

         x[i]=A[i][n];

 }

 int main(){

     freopen("walk.in","r",stdin);

     freopen("walk.out","w",stdout);

     scanf("%d%d",&n,&m);

     for(int i=;i<=m;i++){

         scanf("%d%d",&e[i][],&e[i][]);

         d[e[i][]]+=;d[e[i][]]+=;

     }A[][n]=;

     for(int i=;i<n;i++)A[i][i]=;

     for(int i=;i<=m;i++){

         if(e[i][]==n||e[i][]==n)continue;

         A[e[i][]][e[i][]]+=-1.0/d[e[i][]];

         A[e[i][]][e[i][]]+=-1.0/d[e[i][]];

     }

     Guass_Elimination();

     for(int i=;i<=m;i++){

         w[i]+=x[e[i][]]/d[e[i][]];

         w[i]+=x[e[i][]]/d[e[i][]];

     }

     sort(w+,w+m+);

     for(int i=;i<=m;i++)

         ans+=w[i]*(m-i+);

     printf("%.3lf\n",ans);

     return ;

 }

秒客网