「HNOI2012」矿场搭建 - 点双连通分量 + 割点

发表于 分类于 ， 阅读次数： Disqus：

题意描述

洛谷链接

LibreOJ 链接

煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见，希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设立救援出口，使得无论哪一个挖煤点坍塌之后，其他挖煤点的工人都有一条道路通向救援出口。

请写一个程序，用来计算至少需要设置几个救援出口，以及不同最少救援出口的设置方案总数。

解题思路

对于同一个点双连通分量的点，如果有坍塌则方案情况相同。于是我们可以先进行点双连通分量缩点，然后形成一个 DAG。接下来我们进行讨论：

  1. 若一个点双连通分量没有割点：会堵住一个点，故需要 \(2\) 个出口；
  2. 若一个点双连通分量有 \(1\) 个割点：可从这个割点逃出，故只需 \(1\) 个出口；
  3. 若一个点双连通分量 \(2\) 个及以上个割点：无论如何都可逃出，无需出口。

于是我们缩点后统计每个双连通分量即可。

对于统计方案，我们设某个双连通分量的节点数为 \(s\)，则对于上列情况，分别对应情况数为 \(C_s^2\)、\(C_s^1\) 和 \(C_s^0\)，即 \(\frac{s(s - 1)}{2}\)、\(s\) 和 \(1\)。将所有点双连通分量方案相乘即为总方案。

代码演示

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

const int MAXN = 1000;

int n, m;
std::vector<int> G[MAXN + 1];
bool cut[MAXN + 1];

int dfn[MAXN + 1], low[MAXN + 1];
int ts = 0, root;
std::stack<int> stk;

std::vector<int> dcc[MAXN + 1];
int cnt;

void tarjan(int u) {
    dfn[u] = low[u] = ++ts;
    stk.push(u);
    if (u == root && G[u].empty()) {
        dcc[++cnt].push_back(u);
        return;
    }
    int flag = 0;
    for (int v : G[u]) {
        if (!dfn[v]) {
            tarjan(v);
            low[u] = std::min(low[u], low[v]);
            if (low[v] >= dfn[u]) {
                flag++;
                if (u != root || flag > 1) cut[u] = true;
                cnt++;
                int w;
                do {
                    w = stk.top();
                    stk.pop();
                    dcc[cnt].push_back(w);
                } while (w != v);
                dcc[cnt].push_back(u);
            }
        } else low[u] = std::min(low[u], dfn[v]);
    }
}

void init() {
    n = ts = cnt = 0;
    for (int i = 0; i < MAXN; i++) G[i].clear();
    memset(cut, false, sizeof(cut));
    memset(dfn, 0, sizeof(dfn));
    memset(low, 0, sizeof(low));
    for (int i = 0; i < MAXN; i++) dcc[i].clear();
}

int main() {
    int t = 0;

    while (scanf("%d", &m) != EOF && m) {
        init();

        std::map<int, int> mp;
        mp.clear();
        for (int i = 1; i <= m; i++) {
            int u, v;
            scanf("%d %d", &u, &v);
            if (!mp[u]) mp[u] = ++n;
            if (!mp[v]) mp[v] = ++n;
            G[mp[u]].push_back(mp[v]);
            G[mp[v]].push_back(mp[u]);
        }

        for (int i = 1; i <= n; i++) {
            if (!dfn[i]) {
                root = i;
                tarjan(i);
            }
        }

        unsigned long long ans = 0, cases = 1;
        for (int i = 1; i <= cnt; i++) {
            int cnts = 0;
            for (int u : dcc[i]) if (cut[u]) cnts++;
            if (cnts == 0) ans += 2, cases *= 1ull * dcc[i].size() * (dcc[i].size() - 1) / 2;
            else if (cnts == 1) ans++, cases *= dcc[i].size() - 1;
        }
        printf("Case %d: %llu %llu\n", ++t, ans, cases);
    }

    return 0;
}