[HNOI 2012] 矿场搭建

题目大意

煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见,希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设立救援出口,使得无论哪一个挖煤点坍塌之后,其他挖煤点的工人都有一条道路通向救援出口。求至少需要设置几个救援出口,以及不同最少救援出口的设置方案总数,多组询问。

1m5001 \leqslant m \leqslant 500

题目链接

【HNOI 2012】矿场搭建 - Luogu 3225

题解

输入是保证图连通的。

若坍塌的不是割点,则逃生点随意,所以只考虑坍塌在割点。若一个块能通往两个及以上的割点,则不用设立逃生点;若只能到达一个割点,则再设一个逃生点;若无割点,则随意设置两个(坍塌在逃生点)。

用 Tarjan 求割点,然后遍历图求出每个块的大小已经能到达的割点数。

数据保证了答案不超过 long long。但最大答案,是会把 long long 超好几圈的。。。

一开始答案写的 int,COGS 上发现最后一个点的答案过了 int,于是写完题后想了想理论最大答案。最大的答案应该是一个菊花图(只有一个割点),除了中心的一个点,剩下的 500500 个点(500500 条边的树是 501501 个点)均匀分在每个延出去的链上,若分成了 xx 条链,则答案大概是 (500x)x(\frac{500}{x})^x(没有考虑取整),式子在正整数范围内的最大值是 x=184x = 184时,值为 7.656×10797.656 \times 10^{79}。所以,这题差点成了高精度。。。(如果不取模的话)

代码

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
#include <cstdio>
#include <set>
#include <queue>
#include <algorithm>
// #define DBG
const int MAXN = 505;
struct Edge;
struct Node {
Edge *e;
Node *fa;
int dfn, low;
bool vis, ins, isCut;
#ifdef DBG
int id;
#endif
} N[MAXN];
struct Edge {
Node *u, *v;
Edge *next;
Edge(Node *u, Node *v) : u(u), v(v), next(u->e) {}
};
void addEdge(int u, int v) {
N[u].e = new Edge(&N[u], &N[v]);
N[v].e = new Edge(&N[v], &N[u]);
}
int n;
void clear() {
for (int i = 1; i <= n; i++) {
for (Edge *&e = N[i].e, *next; e; next = e->next, delete e, e = next);
N[i].vis = N[i].ins = N[i].isCut = false;
N[i].fa = NULL;
N[i].dfn = N[i].low = 0;
}
}
namespace Tarjan {
int dfsClock;
void dfs(Node *u) {
u->dfn = u->low = ++dfsClock;
#ifdef DBG
printf("tarjan-dfs(%d)\n", u->id);
#endif
int childCnt = 0;
for (Edge *e = u->e; e; e = e->next) {
if (!e->v->dfn) {
childCnt++;
e->v->fa = u;
dfs(e->v);
u->low = std::min(u->low, e->v->low);
if (u->fa) {
if (e->v->low >= u->dfn) u->isCut = true;
} else if (childCnt == 2) u->isCut = true;
} else u->low = std::min(u->low, e->v->dfn);
}
}
void findCut() {
dfsClock = 0;
dfs(&N[1]);
}
}
void solve(int &min, long long &cnt) {
min = 0, cnt = 1;
for (int i = 1; i <= n; i++) {
if (N[i].vis || N[i].isCut) continue;
std::queue<Node *> q;
q.push(&N[i]);
N[i].vis = true;
std::set<Node *> s;
int size = 0;
while (!q.empty()) {
Node *u = q.front();
q.pop();
size++;
for (Edge *e = u->e; e; e = e->next) {
if (e->v->isCut) s.insert(e->v);
else if (!e->v->vis) q.push(e->v), e->v->vis = true;
}
}
if (s.size() == 1) min++, cnt *= size;
}
if (!min) min = 2, cnt = n * (n - 1) / 2;
}
int main() {
for (int i = 1, m; ~scanf("%d", &m) && m; i++) {
n = 0;
while (m--) {
int u, v;
scanf("%d %d", &u, &v);
addEdge(u, v);
n = std::max(n, std::max(u, v));
}
#ifdef DBG
for (int i = 1; i <= n; i++) N[i].id = i;
#endif
Tarjan::findCut();
#ifdef DBG
for (int i = 1; i <= n; i++) if (N[i].isCut) printf("cut: %d\n", i);
#endif
int min;
long long cnt;
solve(min, cnt);
printf("Case %d: %d %lld\n", i, min, cnt);
clear();
}
return 0;
}