[BZOJ3143][HNOI2013]游走(期望+高斯消元)

3143: [Hnoi2013]游走
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 3576 Solved: 1608
[Submit][Status][Discuss]
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。

Source

非官方数据

[Submit][Status][Discuss]

如果是给你一幅图，让你求随机游走到每个点的期望次数，那就是裸的期望高斯消元原题。

这道题不难发现贪心的将走的次数最多的边权值设为最小一定最优，而边的次数又可以由两端点的期望次数求出，所以问题轻松转化为上面那个原题。

边$<u,v>$走的期望次数为$frac{E[u]}{deg[u]}+frac{E[v]}{deg[v]}$

高斯消元竟然忘了。

 1 #include<cmath>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #define rep(i,l,r) for (int i=l; i<=r; i++)
 5 using namespace std;
 6 
 7 const int N=510,M=300100;
 8 int n,m,u[M],v[M],d[N];
 9 double ans,a[N][N],x[N],w[M];
10 
11 void Gauss(){
12     rep(i,1,n){
13         int k=i;
14         rep(j,i+1,n) if (fabs(a[k][i])<fabs(a[j][i])) k=j;
15         if (k!=i) rep(j,i,n+1) swap(a[i][j],a[k][j]);
16         rep(j,i+1,n){
17             double t=a[j][i]/a[i][i];
18             rep(k,i,n+1) a[j][k]-=a[i][k]*t;
19         }
20     }
21     for (int i=n; i; i--){
22         rep(j,i+1,n) a[i][n+1]-=a[i][j]*x[j];
23         x[i]=a[i][n+1]/a[i][i];
24     }
25 }
26 
27 int main(){
28     freopen("walk.in","r",stdin);
29     freopen("walk.out","w",stdout);
30     scanf("%d%d",&n,&m);
31     rep(i,1,m) scanf("%d%d",&u[i],&v[i]),d[u[i]]++,d[v[i]]++;
32     rep(i,1,m) a[u[i]][v[i]]+=1./d[v[i]],a[v[i]][u[i]]+=1./d[u[i]];
33     rep(i,1,n-1) a[i][i]=-1;
34     rep(i,1,n) a[n][i]=0;
35     a[1][n+1]=-1; a[n][n]=1; Gauss();
36     rep(i,1,m) w[i]=x[u[i]]/d[u[i]]+x[v[i]]/d[v[i]];
37     sort(w+1,w+m+1);
38     rep(i,1,m) ans+=(m-i+1)*w[i];
39     printf("%.3lf
",ans); 
40     return 0;
41 }