矿场搭建(割点+找点联通分量)
G-[HNOI2012]矿场搭建_2022图论班第二章连通性例题与习题 (nowcoder.com)
题目描述
煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见，希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设立救援出口，使得无论哪一个挖煤点坍塌之后，其他挖煤点的工人都有一条道路通向救援出口。
请写一个程序，用来计算至少需要设置几个救援出口，以及不同最少救援出口的设置方案总数。
输入格式
输入文件有若干组数据，每组数据的第一行是一个正整数 N（N<=500），表示工地的隧道数，接下来的 N 行每行是用空格隔开的两个整数 S 和 T，表示挖 S 与挖煤点 T 由隧道直接连接。输入数据以 0 结尾。
输出格式
输入文件中有多少组数据，输出文件 output.txt 中就有多少行。每行对应一组输入数据的 结果。其中第 i 行以 Case i: 开始（注意大小写，Case 与 i 之间有空格，i 与:之间无空格，: 之后有空格），其后是用空格隔开的两个正整数，第一个正整数表示对于第 i 组输入数据至少需 要设置几个救援出口，第二个正整数表示对于第 i 组输入数据不同最少救援出口的设置方案总 数。输入数据保证答案小于 2^64。输出格式参照以下输入输出样例。
输入输出样例
输入 #1复制
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复制
Case 1: 2 4
Case 2: 4 1
说明/提示
Case 1 的四组解分别是(2,4),(3,4),(4,5),(4,6)；
Case 2 的一组解为(4,5,6,7)。
题解:
显然，先 Tarjan跑出割点，然后 DFS搜索所有的联通块
计算每一个联通块中的割点数目。
然后再分类讨论:
·如果没有割点，至少需要建立两个出口，从任意地方选择两个点建立，如果设连通块的大小为siz，则对答案的贡献为(siz—1)*siz/2
。如果轰炸其中一个出口，则其他点都可以从另一个出口逃走。。如果轰炸的是其他点，不啥事都没有吗~
·如果这个连通块只有一个割点，只需要在连通块内设立一个出口，可以设立在任意一个非割点的地方，如果设连通块的大小为siz，则贡献为siz —1(因为不能建立在割点上)。
。如果轰炸的是割点，则连通块内的其他点都可以通过刚刚建立的出口出去。
。如果轰炸的是我们刚刚建立的出口，那由于我们刚刚建立的出口不是割点，所以连通块内除了轰炸了的点，都可以从割点通向另—个连通块内的出口。
。如果这个连通块有两个及以上个割点，则不需要建立出口。
。如果轰炸的是其中一个割点，则可以通过其他割点到达其他的连通块。。如果轰炸的是其他点，则轰炸的不是割点，啥事都没有~
最后将所有连通块的贡献乘起来(简单的乘法原理)。
如果有两个及以上个割点，则无需建立，可以直接到达其他联通块
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef unsigned long long ULL;
const int N = 1010, M = 1010;
int n, m;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int stk[N], top;
int dcc_cnt;
vector<int> dcc[N];
bool cut[N];
int root;
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void tarjan(int u)
{
dfn[u] = low[u] = ++ timestamp;
stk[ ++ top] = u;
if (u == root && h[u] == -1)
{
dcc_cnt ++ ;
dcc[dcc_cnt].push_back(u);
return;
}//如果有一个单独点
int cnt = 0;
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (!dfn[j])
{
tarjan(j);
low[u] = min(low[u], low[j]);
if (dfn[u] <= low[j])
{
cnt ++ ;
if (u != root || cnt > 1) cut[u] = true;
++ dcc_cnt;
int y;
do {
y = stk[top -- ];
dcc[dcc_cnt].push_back(y);
} while (y != j);//注意是弹出到j不是到u,肯定会有几个点双联通分量公用一个割点
dcc[dcc_cnt].push_back(u);//但是u也要加入点双联通分量中
}
}
else low[u] = min(low[u], dfn[j]);
}
}
int main()
{
int T = 1;
while (cin >> m, m)
{
for (int i = 1; i <= dcc_cnt; i ++ ) dcc[i].clear();
idx = n = timestamp = top = dcc_cnt = 0;
memset(h, -1, sizeof h);
memset(dfn, 0, sizeof dfn);
memset(cut, 0, sizeof cut);
while (m -- )
{
int a, b;
cin >> a >> b;
n = max(n, a), n = max(n, b);
add(a, b), add(b, a);
}
for (root = 1; root <= n; root ++ )
if (!dfn[root])
tarjan(root);
int res = 0;
ULL num = 1;
for (int i = 1; i <= dcc_cnt; i ++ )
{
int cnt = 0;
for (int j = 0; j < dcc[i].size(); j ++ )
if (cut[dcc[i][j]])
cnt ++ ;
if (cnt == 0)
{
if (dcc[i].size() > 1) res += 2, num *= dcc[i].size() * (dcc[i].size() - 1) / 2;
else res ++ ;
}
else if (cnt == 1) res ++, num *= dcc[i].size() - 1;
}
printf("Case %d: %d %llu\n", T ++, res, num);
}
return 0;
}