NKOJ 2266 （HNOI 2013）游走（高斯消元+数学期望）

发表于 |
字数统计: 879字 | 阅读时长 ≈ 4min

P2266【HNOI2013 DAY2】游走

问题描述

一个无向连通图，顶点从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, 1<=M<=150000且是一个无向简单连通图。

输出格式

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

样例输入 1

3 3
2 3
1 2
1 3

样例输出 1

3.333

样例输入 2

5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

样例输出 2

17.800

显然的需要求出每条边的期望经过次数，假设这条边两端是$x,y$，那么有$E[i]=\frac{E[x]}{D[x]}+\frac{E[y]}{D[y]}$，其中$i$表示一条边，$E$表示经过次数的期望，$D$表示节点的度。证明是显然的。

那么只需要求出每个点经过次数的期望，那么显然将$E[x]$当作未知数来寻找关系。
对于起点一号点，有$E[1]=1+\sum{\frac{E[t]}{D[t]}},t是与1相连的点，且不是终点$，对于其他点，只需要不加1即可。然后高斯消元。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 555
#define M 200005
using namespace std;
struct node{int a,b;double c;}e[M];
bool cmp(node a,node b)
{return a.c>b.c;}
int n,m,D[N];
bool G[N][N];
double A[N][N],X[N];
void Gauss(int row,int col)
{
	int i,j,x,y,MR;double t;
	for(x=1,y=1,MR=1;x<=row&&y<col;x++,y++,MR=x)
	{
		for(i=x+1;i<=row;i++)if(abs(A[i][y])>abs(A[MR][y]))MR=i;
		if(MR!=x)for(i=1;i<=col;i++)swap(A[x][i],A[MR][i]);
		if(!A[x][y]){x--;continue;}
		for(i=x+1;i<=row;i++)
		if(A[i][y])
		{
			t=A[i][y]/A[x][y];
			for(j=y;j<=col;j++)A[i][j]-=A[x][j]*t;
		}
	}
	for(i=row;i>=1;i--)
	{
		X[i]=A[i][col];
		for(j=i+1;j<col;j++)X[i]-=X[j]*A[i][j];
		X[i]/=A[i][i];
	}
}
int main()
{
	int i,j,x,y;double ans=0;
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		G[x][y]=G[y][x]=1;
		e[i].a=x;e[i].b=y;
		D[x]++;D[y]++;
	}
	for(i=1;i<n;i++)A[i][i]=1.0;
	for(i=1;i<n;i++)
	for(j=1;j<n;j++)
	if(i!=j&&G[i][j])A[i][j]=-1.0/D[j];
	A[1][n]=1;Gauss(n-1,n);
	for(i=1;i<=m;i++)
	{
		x=e[i].a;y=e[i].b;
		if(x!=n)e[i].c+=1.0*X[x]/(1.0*D[x]);
		if(y!=n)e[i].c+=1.0*X[y]/(1.0*D[y]);
	}
	sort(e+1,e+m+1,cmp);
	for(i=1;i<=m;i++)ans+=1.0*i*e[i].c;
	printf("%.3lf",ans);
}