HDU 5036
给定一有向图,对点 $u$ 的操作定义为从图中删除 $u$ 和所有由 $u$ 可达的点 $v$。每次随机选一个未被删除的点进行该操作,直到所有点被删除,求进行该操作的期望次数。

题解

根据期望的线性性质,答案等于每个点被操作过的期望次数之和。记 $c(u)$ 为点 $u$ 被操作过的次数。
一个明显的性质是,操作一个点后所有由该点出发可达的点都会被删除。
记 $S(u) = \{v | 存在由 v 到 u 的路径\}$ ,则 $u$ 可能在 $S(u)$ 中任何一点被操作后被删除。设 $u$ 在对 $r(u)$ 的操作中被删除,则 $S(u)$ 中每个点成为 $r(u)$ 的概率相同,因而有
$$P[r(u) = u] = \frac{1}{|S(u)|}$$
事实上,这意味着 $u$ 被操作过的概率为 $\frac{1}{|S(u)|}$ 。注意到 $c(u) \leq 1$,因而
$$P[c(u) = 1] = \frac{1}{|S(u)|}$$
$$P[c(u) = 0] = 1 - \frac{1}{|S(u)|}$$
根据期望的定义,有
$$E[c(u)] = \frac{1}{|S(u)|} \times 1 + (1 - \frac{1}{|S(u)|}) \times 0 = \frac{1}{|S(u)|}$$
则答案为
$$\sum_{u \in V} \frac{1}{|S(u)|}$$
其中点 $u$ 的 $|S(u)|$ 容易通过原图的传递闭包求得。求原图的传递闭包,只需使用 bitset 优化的 Floyd 算法即可通过。

代码

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
#include <cstdio>
#include <bitset>
const int MAXN = 1005;
int n;
std::bitset<MAXN> g[MAXN];
inline void floyd() {
for (int k = 1; k <= n; ++k)
for (int i = 1; i <= n; ++i)
if (g[i][k])
g[i] |= g[k];
}
int main() {
int t, d, i, u, v, k;
double ans;
scanf("%d", &t);
for (int kase = 1; kase <= t; ++kase) {
scanf("%d", &n);
for (u = 1; u <= n; ++u) {
g[u].reset();
g[u].set(u);
scanf("%d", &d);
for (i = 1; i <= d; ++i) {
scanf("%d", &v);
g[u].set(v);
}
}
floyd();
ans = 0.0;
for (v = 1; v <= n; ++v) {
k = 0;
for (u = 1; u <= n; ++u)
if (g[u][v])
++k;
ans += 1.0 / k;
}
printf("Case #%d: %.5lf\n", kase, ans);
}
return 0;
}