「HNOI2013」游走

发表于 | 分类于 | | 浏览量： 次

期望什么的最不会了qwq。

传送门

洛谷P3232

BZOJ3143

题解

首先先考虑如何求一个点的期望经过次数，不难发现有：

注意节点$1$和节点$n$要特殊考虑。

可以用高斯消元法求解出每个点的期望经过次数，从而计算出每条边的期望经过次数。

将边的期望经过次数由大到小排序，依次编号为$1-M$然后计算出总和即可。

代码

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
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=505;
int n,m,tot,lnk[maxn],son[maxn*maxn],nxt[maxn*maxn],deg[maxn];double A[maxn][maxn],ans,cnt[maxn*maxn];
inline int read()
{
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
	return ret*f;
}
inline void add_e(int x,int y){tot++;son[tot]=y;deg[y]++;nxt[tot]=lnk[x];lnk[x]=tot;}
inline double ABS(double x){return x<0?-x:x;}
inline void Gauss()
{
	for(int i=1;i<n;i++)
	{
		for(int j=i+1;j<=n;j++)
		{
			double t=(double)-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;i--)
	{
		for(int j=i+1;j<=n;j++)
			A[i][n+1]-=A[i][j]*A[j][n+1];
		A[i][n+1]/=A[i][i];
	}
}
inline void Solve()
{
	for(int i=1;i<n;i++)
		for(int j=lnk[i];j;j=nxt[j])
			cnt[(j+1)>>1]+=A[i][n+1]/deg[i];
	sort(cnt+1,cnt+1+m);
	for(int i=1;i<=m;i++)
		ans+=cnt[i]*(m-i+1);
}
int main()
{
	n=read();m=read();
	for(int i=1;i<=n;i++) A[i][i]=-1;
	A[n][n+1]=1;A[1][n+1]=-1;
	for(int i=1;i<=m;i++)
	{
		int a=read(),b=read();
		add_e(a,b);add_e(b,a);
	}
	for(int i=1;i<n;i++)
		for(int j=lnk[i];j;j=nxt[j])
			A[son[j]][i]=(double)1/deg[i];
	Gauss();
	Solve();
	printf("%.3lf\n",ans);
	return 0;
}