「LOJ 2673」「NOI2012」迷失游乐园

发表于

放假了，小 Z 觉得呆在家里特别无聊，于是决定一个人去游乐园玩。进入游乐园后，小 Z 看了看游乐园的地图,发现可以将游乐园抽象成有 nn 个景点、 mm 条道路的无向连通图，且该图中至多有一个环（即 mm 只可能等于 nn 或者 n−1n-1 ）。

小 Z 现在所在的大门也正好是一个景点。小 Z 不知道什么好玩，于是他决定，从当前位置出发，每次随机去一个和当前景点有道路相连的景点，并且同一个景点不去两次（包括起始景点）。贪玩的小 Z 会一直游玩，直到当前景点的相邻景点都已经访问过为止。

小 Z 所有经过的景点按顺序构成一条非重复路径，他想知道这条路径的期望长度是多少？

小 Z 把游乐园的抽象地图画下来带回了家，可是忘了标哪个点是大门，他只好假设每个景点都可能是大门（即每个景点作为起始点的概率是一样的）。同时，他每次在选择下一个景点时会等概率地随机选择一个还没去过的相邻景点。

Constraints

1≤n≤1000001 \leq n \leq 100000

Solution

题意给出的图为树或基环树，可以用树形 dp 求解这道题。

对于树的情况，我们令 dnxdn_x 表示向下走的期望， upxup_x 表示向上走的期望， dxd_x 表示度数， chxch_x 表示儿子节点的个数。则易得以下递推方程：

dnx=∑i∈childx(dni+wx,i)chxdn_x=\frac{\sum _{i\in child_x}(dn_i+w_{x,i})}{ch_x}

upx=wfa,x+upfa⋅(dfa−chfa)+dnfa⋅chfa−wfa,x−dnxdfa−1up_x=w_{fa,x}+\frac{up_{fa} \cdot (d_{fa}-ch_{fa})+dn_{fa} \cdot ch_{fa}-w_{fa,x}-dn_x}{d_{fa}-1}

对于环的情况， dndn 数组同树的情况，而由于环上的点最多只有 2020 个，所以 upup 数组可以暴力 O(n2)O(n^2) 进行统计。具体方式为，顺逆时针各统计一次，初始概率均为 0.50.5 ，每到达一个点，概率除以儿子个数 +1+1 ，并加上对应的 dndn 和边权。对于基环树，先处理完树部分的 dndn ，再处理环部分的 upup ，最后将环部分的 upup 下传。

Code

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include<cstdio>
#include<algorithm> 
#include<cstring>
#define LL long long
using namespace std;
const int N=1e5+5;
int n,m,cnt,x,y,w,t,sum,vertex;
int first[N],d[N],ch[N];
int a[N],s[N],pre[N],len[N];
double ans,dn[N],up[N];
bool cir[N],vis[N];
struct edge{int to,next,w;}e[N*2];
int read()
{
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*f;
}
void insert(int u,int v,int w)
{
	e[++cnt]=(edge){v,first[u],w};
	first[u]=cnt;d[v]++;
}
void find(int x,int fa,int w)
{
	if(vertex)return;
	pre[x]=fa;len[x]=w;
	if(vis[x]){vertex=x;return;}
	vis[x]=true;
	for(int i=first[x];i;i=e[i].next)
	{
		int to=e[i].to;
		if(to==fa)continue;
		find(to,x,e[i].w);
	}
}
void dfs1(int x,int fa)
{
	for(int i=first[x];i;i=e[i].next)
	{
		int to=e[i].to;
		if(to==fa||cir[to])continue;
		dfs1(to,x);ch[x]++;
		dn[x]+=dn[to]+e[i].w;
	}
	if(ch[x])dn[x]/=ch[x];
}
void dfs2(int x,int fa)
{
	for(int i=first[x];i;i=e[i].next)
	{
		int to=e[i].to;
		if(to==fa||cir[to])continue;
		up[to]=e[i].w;
		if(d[x]>1)up[to]+=(up[x]*(d[x]-ch[x])+dn[x]*ch[x]-dn[to]-e[i].w)/(d[x]-1);
		dfs2(to,x);
	}
}
int main()
{
	n=read();m=read();
	for(int i=1;i<=m;i++)
	{
		x=read();y=read();w=read();
		insert(x,y,w);insert(y,x,w);
	}
	if(m==n-1)dfs1(1,-1),dfs2(1,-1);
	else
	{
		find(1,-1,0);cnt=0;t=vertex;
		a[++cnt]=t;cir[t]=true;t=pre[t];
		while(t!=vertex)a[++cnt]=t,cir[t]=true,t=pre[t];
		for(int i=1;i<=cnt;i++)a[i+cnt]=a[i],s[i+1]=s[i+cnt+1]=len[a[i]];
		for(int i=1;i<=cnt;i++)dfs1(a[i],0);
		for(int i=1;i<=cnt;i++)
		{
			double p=0.5;sum=s[i+1];
			up[a[i]]+=p*(sum+dn[a[i+1]])*ch[a[i+1]]/(ch[a[i+1]]+1);
			p/=(ch[a[i+1]]+1);
			for(int j=i+2;j<=i+cnt-2;j++)
			{
				sum+=s[j];
				up[a[i]]+=p*(sum+dn[a[j]])*ch[a[j]]/(ch[a[j]]+1);
				p/=(ch[a[j]]+1);
			}
			sum+=s[i+cnt-1];
			up[a[i]]+=p*(sum+dn[a[i+cnt-1]]);
			p=0.5;sum=s[i+cnt];
			up[a[i]]+=p*(sum+dn[a[i+cnt-1]])*ch[a[i+cnt-1]]/(ch[a[i+cnt-1]]+1);
			p/=(ch[a[i+cnt-1]]+1);
			for(int j=i+cnt-2;j>=i+2;j--)
			{
				sum+=s[j+1];
				up[a[i]]+=p*(sum+dn[a[j]])*ch[a[j]]/(ch[a[j]]+1);
				p/=(ch[a[j]]+1);
			}
			sum+=s[i+2];
			up[a[i]]+=p*(sum+dn[a[i+1]]);
		}
		for(int i=1;i<=cnt;i++)dfs2(a[i],-1);
	}
	for(int i=1;i<=n;i++)ans+=(dn[i]*ch[i]+up[i]*(d[i]-ch[i]))/d[i];
	printf("%.5lf",ans/n);
	return 0;
}