bzoj 3143 游走

Posted on | Edited on | Views:

图上随机游走.

每条边的贡献是它被赋上的权值乘上它期望被经过的次数.

根据排序不等式,显然应该给期望被经过次数更大的边赋更小的权值,给期望被经过次数更小的边赋更大的权值.

设 $f(i)$ 表示点 $i$ 期望被经过的次数,则边 $(u,v)$ 期望被经过的次数为 $[u\neq n]\frac{f(u)}{\deg(u)}+[v\neq n]\frac{f(v)}{\deg(v)}$ .

转移有,
$$
f(i)=[i=1]+\sum_{(j,i)\in E,j\neq n} \frac{f(j)}{\deg(j)}
$$

高斯消元解出所有的 $f(i)$ ,时间复杂度 $O(n^3)$ .

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
//%std
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const double eps=1e-8;
const int MAXN=1<<9,MAXM=MAXN*MAXN/2;
int n,m,x[MAXM],y[MAXM],deg[MAXN];
double a[MAXN][MAXN],f[MAXN],val[MAXM];
void Gauss()
{
	for(int i=1;i<=n;++i)
	{
		int j;
		for(j=i;j<=n;++j)
			if(fabs(a[j][i])>eps)
				break;
		for(int k=1;k<=n+1;++k)
			swap(a[i][k],a[j][k]);			
		for(int j=i+1;j<=n;++j)
		{
			double t=a[j][i]/a[i][i];
			for(int k=i;k<=n+1;++k)
				a[j][k]-=t*a[i][k];	
		}	
	}
	for(int i=n;i>=1;--i)
	{
		f[i]=a[i][n+1]/a[i][i];
		for(int j=i-1;j>=1;--j)
			a[j][n+1]-=a[j][i]*f[i];
	}
}
int main()
{
	n=read(),m=read();
	for(int i=1;i<=m;++i)
	{
		int u=read(),v=read();
		x[i]=u,y[i]=v;
		++deg[u],++deg[v];
		if(v!=n)
			a[u][v]=-1;
		if(u!=n)
			a[v][u]=-1;
	}
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j)
			a[j][i]/=deg[i];
	a[1][n+1]=1;
	for(int i=1;i<=n;++i)
		a[i][i]=1;
	Gauss();
	for(int i=1;i<=m;++i)
	{
		if(x[i]!=n)
			val[i]+=f[x[i]]/deg[x[i]];
		if(y[i]!=n)
			val[i]+=f[y[i]]/deg[y[i]];
	}
	sort(val+1,val+1+m);
	double ans=0;
	for(int i=1;i<=m;++i)
		ans+=val[i]*(m+1-i);
	printf("%.3f\n",ans);
	return 0;
}