题面：[HNOI2012] 矿场搭建

大秦为你打开题目传送门

题目描述

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

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

输入格式

输入文件有若干组数据。

每组数据的第一行是一个正整数 $N\ (N \le 500)$，表示工地的隧道数。

接下来的 $N$ 行每行是用空格隔开的两个整数 $S$ 和 $T$，表示挖煤点 $S$ 与挖煤点 $T$ 由隧道直接连接。

输入数据以 $0$ 结尾。

输出格式

对于每组数据，输出一行。

第 $i$ 行组数据以 Case i: 开始。

其后是用空格隔开的两个正整数，第一个正整数表示对于第 $i$ 组输入数据至少需要设置几个救援出口，第二个正整数表示对于第 $i$ 组输入数据不同最少救援出口的设置方案总数。

输入数据保证答案小于 $2^{64}$。输出格式参照以下输入输出样例。

样例 #1

样例输入 #1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
9
1 3
4 1
3 5
1 2
2 6
1 5
6 3
1 6
3 2
6
1 2
1 3
2 4
2 5
3 6
3 7
0

样例输出 #1

1
2
Case 1: 2 4
Case 2: 4 1

提示

样例解释

  • Case 1 的四组解分别是 $(2,4)$，$(3,4)$，$(4,5)$，$(4,6)$；
  • Case 2 的一组解为 $(4,5,6,7)$。

数据范围及约定

对于每组数据，设 $m$ 为各组 $S, T$ 中最大值，则有：

  • $1 \le m \le 10^3$；
  • 各组 $S, T$ 构成的集合 $V = [1, m] \cap \mathbb Z$。
  • $V$ 中任意两点连通。

思路

我们可以大致的分类讨论一下，对于一个点双连通分量，他有下面两种可能：

  1. 没有割点（这里割点的概念是对于全图来讲的割点）
  2. 一个割点
  3. 两个及以上割点

它对应的情况就是下面这样（圆圈是点双连通分量，点是割点）：

原因的话很好说，因为只会坍塌一个点，所以说如果没有割点的存在，也就是第一种情况，我们就需要两个来保险，万一塌的就是修了的那个点怎么办？所以说我们第一种情况修两个不一样的点就可以。

第二种情况，我们有了一个割点，那么显然我们只需要在每一个连通分量各修一个不是割点的即可，因为最坏情况塌的是割点，我们要在碎出来的两个块各修一个；如果塌的是某一个连通分量里的点，那么我们可以通过割点到另外一个连通分量。

第三种也是显而易见，不管塌了哪个点，我们一定可以通过剩下的割点离开，也就是说如果有两个及以上的割点，我们就不用修了。

代码

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
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
// typedef __int128 int128;
typedef pair<int , int > pii;
typedef unsigned long long ull;

namespace FastIO 
{
    // char buf[1 << 20], *p1, *p2;
    // #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++)
    template<typename T> inline T read(T& x) {
        x = 0;
        int f = 1;
        char ch;
        while (!isdigit(ch = getchar())) if (ch == '-') f = -1;
        while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
        x *= f;
        return x;
    }
    template<typename T, typename... Args> inline void read(T& x, Args &...x_) {
        read(x);
        read(x_...);
        return;
    }
    inline ll read() {
        ll x;
        read(x);
        return x;
    }
};
using namespace FastIO;

const int MaxV = 1010;
const int MaxE = 510;

template<int N, int M>
class Graph {
    private :
        struct Edge {
            int to, nt, wt;
            Edge() {}
            Edge(int to, int nt, int wt) : to(to), nt(nt), wt(wt) {}
        }e[M];
        int hd[N], cnte;
    public :
        inline void clear() { memset(hd, 0, sizeof(hd)), cnte = 0; }
        inline void AddEdge(int u, int v, int w = 0) {
            e[++cnte] = Edge(v, hd[u], w);
            hd[u] = cnte;
        }
        inline int head(int u) { return hd[u]; }
        inline int nt(int u) { return e[u].nt; }
        inline int to(int u) { return e[u].to; }
        inline int wt(int u) { return e[u].wt; }
};

int n, m;
Graph< MaxV, MaxE << 1 >G;

inline void Input() {
    read(m);
    if(m == 0) return exit(0);
    int u, v;
    for(int i = 1; i <= m; i++) {
        read(u, v);
        n = max(n, max(u, v));
        if(u == v) continue;
        G.AddEdge(u, v);
        G.AddEdge(v, u);
    }
}

int dfn[MaxV], low[MaxV], cntd;
stack<int >st;
int cntc, col[MaxV], cut[MaxV];
vector<int >clb[MaxV];

void Tarjan(int u, int fa) {
    dfn[u] = low[u] = ++cntd; st.push(u);
    if(u == fa && G.head(u) == 0) {
        clb[++cntc].push_back(u);
        col[u] = cntc;
        return ;
    } int ch = 0;
    for(int i = G.head(u); i; i = G.nt(i)) {
        int v = G.to(i);
        if(!dfn[v]) {
            Tarjan(v, u);
            low[u] = min(low[u], low[v]);
            if(low[v] >= dfn[u]) {
                if(++ch > 1 || u != fa) cut[u] = 1;
                ++cntc; int now;
                do {
                    now = st.top(); st.pop();
                    col[now] = cntc;
                    clb[cntc].push_back(now);
                }while(now != v);
                clb[cntc].push_back(u);
            }
        }
        else if(v != fa) {
            low[u] = min(low[u], dfn[v]);
        }
    }
}

inline void Work() {
    for(int i = 1; i <= n; i++)
        if(!dfn[i]) Tarjan(1, 1);
    ull ans = 0, way = 1;
    // cout << endl;
    for(int i = 1; i <= cntc; i++) {
        // cout << "club " << i << " : \n";
        ull cnt = 0;
        for(auto &u : clb[i]) {
            // cout << u;
            if(cut[u]) {
                cnt++;
                // cout << "!";
            }
            // cout << ' ';
        }
        // cout << endl;
        ull sz = clb[i].size();
        if(sz == 1) {
            ans++;
        }
        else {
            if(cnt == 0) {
                ans += 2;
                way *= (sz * (sz - 1)) / 2; // it is important to '/2' !
            }
            else if(cnt == 1) {
                ans++;
                way *= (sz - cnt);
            }
        }
    }
    printf("%llu %llu\n", ans, way);
}

inline void Clear() {
    G.clear();
    memset(dfn, 0, sizeof(dfn));
    memset(low, 0, sizeof(low));
    memset(col, 0, sizeof(col));
    memset(cut, 0, sizeof(cut));
    while(!st.empty()) st.pop();
    for(int i = 1; i <= cntc; i++) {
        clb[i].clear();
    }
    cntc = 0;
}

int main() {
    int T = -1, cnt = 0;
    while(T--) {
        Clear();
        Input();
        printf("Case %d: ", ++cnt);
        Work();
    }
    return 0;
}