bzoj3143: [Hnoi2013]游走

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。

设x[i]为第i个点期望走过的次数

x[u]=Σx[v]/deg[v] (v和u连通，且u!=1,u!=n)

1+Σx[v]/deg[v](v和u连通，且u==1)

0(u==n)

显然每条边（u,v）走过的期望e[i]=x[u]/deg[u]+x[v]/deg[v]

然后高斯消元解出x即可

code：

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cmath>
 4 #include<cstring>
 5 #include<algorithm>
 6 #define maxn 505
 7 #define maxm maxn*maxn
 8 #define aabs(x) (x)>0?(x):(-(x))
 9 using namespace std;
10 char ch;
11 int n,m,u[maxm],v[maxm],deg[maxn];
12 double a[maxn][maxn],b[maxn],x[maxn],e[maxm],ans;
13 bool ok;
14 bool cmp(double x,double y){return x>y;}
15 void read(int &x){
16     for (ok=0,ch=getchar();!isdigit(ch);ch=getchar()) if (ch=='-') ok=1;
17     for (x=0;isdigit(ch);x=x*10+ch-'0',ch=getchar());
18     if (ok) x=-x;
19 }
20 void gauss(){
21     int i,j,k;
22     for (i=1,k=1;i<=n;i++){
23         for (j=k;j<=n&&!a[j][i];j++);
24         if (j<=n){
25             if (j!=k){
26                 for (int p=i;p<=n;p++) swap(a[j][p],a[k][p]);
27                 swap(b[j],b[k]);
28             }
29             for (j++;j<=n;j++) if (a[j][i]){
30                 double t=a[j][i]/a[k][i];
31                 for (int p=i;p<=n;p++) a[j][p]-=a[k][p]*t;
32                 b[j]-=b[k]*t;
33             }
34             k++;
35         }
36         else{
37             x[i]=0;
38             for (j=k-1;j;j--) a[j][i]=0;
39         }
40     }
41     for (k--,i=n;i;i--)
42         if (a[k][i]){
43             x[i]=b[k]/a[k][i];
44             for (j=k-1;j;j--) if (a[j][i]) b[j]-=a[j][i]*x[i],a[j][i]=0;
45             k--;
46         }
47 }
48 int main(){
49     read(n),read(m);
50     for (int i=1;i<=m;i++) read(u[i]),read(v[i]),deg[u[i]]++,deg[v[i]]++;
51     for (int i=1;i<n;i++) a[i][i]=-1;
52     for (int i=1;i<=m;i++)
53         if (u[i]!=n&&v[i]!=n) a[u[i]][v[i]]=1.0/deg[v[i]],a[v[i]][u[i]]=1.0/deg[u[i]];
54     b[1]=-1,n--;
55     gauss();
56     for (int i=1;i<=m;i++) e[i]=x[u[i]]/deg[u[i]]+x[v[i]]/deg[v[i]];
57     sort(e+1,e+m+1,cmp);
58     for (int i=1;i<=m;i++) ans+=e[i]*i;
59     printf("%.3lf
",ans);
60     return 0;
61 }