0%

[HNOI2012] 矿场搭建

题目

题目链接

题目大意: 现有一个 $n$ 个点 $m$ 条无向边的矿场, 设计若干个逃生出口使得无论当哪个点坍塌时其他点的人都能从出口撤离. 求出出口个数和方案数. $1 \le m \le 500$, 答案在 $2 ^ {64}$ 以内.

思路

如果一个连通块没有割点, 那么至少要放两个出口.

如果一个连通块有一个割点, 那么只需要放一个出口在任意一个不是割点的地方.

如果有两个以上的割点, 则不需要放出口.

找出所有的割点以后求连通块, 用乘法原理统计答案即可.

代码

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

template <class T>
inline void read(T &x) {
x = 0;
int f = 0;
char ch = getchar();
while (!isdigit(ch)) { f |= ch == '-'; ch = getchar(); }
while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
x = f ? -x : x;
return ;
}

typedef unsigned long long uLL;
typedef long long LL;

std::vector<int> g[510];
LL ans;
int low[510], dfn[510], b[510];
int cnt, n, q, m, sum1, sum2, tot, t;
bool cut[510];

void tarjan(int x, int p) {
int s = 0;
low[x] = dfn[x] = ++cnt;
for (auto i : g[x]) {
if (!dfn[i]) {
tarjan(i, x);
low[x] = std::min(low[x], low[i]);
if (x != p && low[i] >= dfn[x]) cut[x] = true;
if (x == p) ++s;
}
low[x] = std::min(low[x], dfn[i]);
}
if (x == p && s >= 2) cut[x] = true;
}

void dfs(int x) {
b[x] = t;
if (cut[x]) return ;
++sum2;
for (auto i : g[x]) {
if (cut[i] && b[i] != t) ++sum1, b[i] = t;
if (!b[i]) {
dfs(i);
}
}
}

int main() {
while (std::cin >> m && m) {
cnt = n = t = tot = 0;
ans = 1;
for (int i = 1; i <= 500; ++i) g[i].clear(), low[i] = dfn[i] = b[i] = cut[i] = 0;
for (int i = 1, u, v; i <= m; ++i) {
read(u), read(v);
g[u].push_back(v), g[v].push_back(u);
n = std::max(n, std::max(u, v));
}
for (int i = 1; i <= n; ++i) {
if (!dfn[i]) {
tarjan(i, i);
}
}
for (int i = 1; i <= n; ++i) {
if (!b[i] && (!cut[i])) {
++t;
sum1 = sum2 = 0;
dfs(i);
if (!sum1) {
if (sum2 == 1) {
++tot;
ans *= 1;
} else {
tot += 2;
ans *= sum2 * (sum2 - 1) / 2;
}
}
else if (sum1 == 1) ans *= sum2, ++tot;
}
}
printf("Case %d: %d %lld\n", ++q, tot, ans);
}
return 0;
}