题解 BZOJ 2878 [Noi2012]迷失游乐园

题目链接

题意:

给你一张n个点n-1或n条边的带权无向图。从每个点出发一直走下去,不能重复经过某个点。问走过的路径长度的数学期望是多少?
N<=100000。图中至多只有一个环,并且环长不超过20。

题解:
首先考虑是一颗树的情况:
首先随便取一个点为根(例如1号点),做树状动规。
设点i走向它的子树的期望长度为F[i],i的子节点为s1、s2……sk。
设D[i] = ∑( F[sj] + edge(i,sj) ) ,那么F[i] = D[i] / k。
设P[i]为i作为起点的期望长度,那么P[1]=F[1],Du[i]是节点i的度数。
再进行一次DFS,如果y是x的子节点,P[x]已经算出。
设节点y向x走对期望的贡献是other,other=(P[x]*Du[x]-edge(x,y)-F[x])/(Du[x]-1)+edge(x,y)
P[y]=(other+D[y])/Du[y]
这样通过两次DFS,就可以算出所有点的P值。
但是这个题可能是一颗基环树。
首先可以通过dfs找出这个环,如果去掉这个环,那就是一些子树构成的森林。
首先用前面提到的树形动规的方法处理这些子树,求出D和F。
然后注意到环上的点很少,我们就依次让环上的每个点作为起点计算一遍。
对于环上的点x,设calc_pre(x)为从x向环上左侧走得到的期望长度,calc_nxt(x)为从x向环上右侧走得到的期望长度。
sx为x的孩子。
那么P[x]=(∑(F[sx]+edge(x,sx)+calc_pre(x)+calc_nxt(x))/Du(x)。
其中calc_pre,calc_nxt可以O(环上点个数)复杂度求出。
于是就可以再次dfs算出所有点的P。
ans=(∑P[i])/n

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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
/**************************************************************
Problem: 2878
User: zrts
Language: C++
Result: Accepted
Time:588 ms
Memory:10748 kb
****************************************************************/

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
//by zrt
//problem:
using namespace std;
typedef long long LL;
const int inf(0x3f3f3f3f);
const double eps(1e-9);
bool oncircle[100005];
int du[100005];
int fa[100005];
int H[100005],X[200005],P[200005],tot;
double E[200005];
inline void add(int x,int y,int z){//add an edge
P[++tot]=y;X[tot]=H[x];H[x]=tot;E[tot]=z;
}
int n,m;
double F[100005];//for son E
double D[100005];// F * |son|
double p[100005];// ans
int num[100005];// |son|
int pre[100005];
double wpre[100005];
bool type;
void treedp1(int x){//Dp the tree first
for(int i=H[x];i;i=X[i]){
if(P[i]==fa[x]||oncircle[P[i]]) continue;
fa[P[i]]=x;
treedp1(P[i]);
D[x]+=F[P[i]]+E[i];num[x]++;
}
if(num[x])
F[x]=D[x]/num[x];
else F[x]=0;
}
void treedp2(int x,double edge){//Dp the tree second | calc the P
double other;
if(!fa[fa[x]]) {
if(!type){
if(num[fa[x]]>1) other=(p[fa[x]]*(num[fa[x]]+0)-edge-F[x])/(num[fa[x]]-1)+edge;
else other=edge;
}else{
other=(p[fa[x]]*(num[fa[x]]+2)-edge-F[x])/(num[fa[x]]+1)+edge;
}
}
else other=(p[fa[x]]*(num[fa[x]]+1)-edge-F[x])/num[fa[x]]+edge;

p[x]=(other+D[x])/(num[x]+1);
for(int i=H[x];i;i=X[i]){
if(P[i]==fa[x]||oncircle[P[i]]) continue;
treedp2(P[i],E[i]);
}
}
vector<int> circle;
bool ok;
int nxt[100005];double wnxt[100005];
void findcircle(int x,int fa){
for(int i=H[x];i;i=X[i]){
if(P[i]==fa) continue;
if(pre[P[i]]){
ok=1;
int k=x;
pre[P[i]]=x;
wpre[P[i]]=E[i];
do{
oncircle[k]=1;
circle.push_back(k);
k=pre[k];
}while(k!=P[i]);
oncircle[k]=1;
circle.push_back(k);
}else{
pre[P[i]]=x;wpre[P[i]]=E[i];
findcircle(P[i],x);
if(ok) return;
}
}
}
double calc_nxt(int now,int end){
double ret=wnxt[now];
now=nxt[now];
int extra=0;
if(nxt[now]!=end) ret+=calc_nxt(now,end)/(du[now]-1);
else extra=-1;
for(int i=H[now];i;i=X[i]){
if(oncircle[P[i]]) continue;
ret+=(E[i]+F[P[i]])/(du[now]-1+extra);
}
return ret;
}
double calc_pre(int now,int end){
double ret=wpre[now];
now=pre[now];
int extra=0;
if(pre[now]!=end) ret+=calc_pre(now,end)/(du[now]-1);
else extra=-1;
for(int i=H[now];i;i=X[i]){
if(oncircle[P[i]]) continue;
ret+=(E[i]+F[P[i]])/(du[now]-1+extra);
}
return ret;
}
int main(){// the main function
#ifdef LOCAL
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
scanf("%d%d",&n,&m);
for(int i=0,x,y,z;i<m;i++){
scanf("%d%d%d",&x,&y,&z);
du[x]++;
du[y]++;
add(x,y,z);
add(y,x,z);
}
if(m==n-1){
treedp1(1);
p[1]=F[1];
for(int i=H[1];i;i=X[i]){
treedp2(P[i],E[i]);
}
double ans=0;
for(int i=1;i<=n;i++){
ans+=p[i];
}
printf("%.5f\n",ans/n);
}else{
type=1;
pre[1]=-1;
findcircle(1,-1);
for(int now=0;now<circle.size();now++){
nxt[pre[circle[now]]]=circle[now];
wnxt[pre[circle[now]]]=wpre[circle[now]];
}
for(int now=0;now<circle.size();now++){
for(int i=H[circle[now]];i;i=X[i]){
if(oncircle[P[i]]) continue;
treedp1(P[i]);
p[circle[now]]+=(F[P[i]]+E[i])/du[circle[now]];
num[circle[now]]++;
}
}
for(int now=0;now<circle.size();now++){
p[circle[now]]+=(calc_pre(circle[now],circle[now])+calc_nxt(circle[now],circle[now]))/du[circle[now]];
}
for(int now=0;now<circle.size();now++){
for(int i=H[circle[now]];i;i=X[i]){
if(oncircle[P[i]]) continue;
fa[P[i]]=circle[now];
treedp2(P[i],E[i]);
}
}
double ans=0;
for(int i=1;i<=n;i++){
ans+=p[i];
}
printf("%.5f\n",ans/n);
}
return 0;
}
评论小助手

评论正在加载...

Tip: 点击下方链接切换到 Disqus 评论框可以获得邮件提醒哦
🗣️ 加载 Disqus 评论框