题目描述
煤矿工地可以看成是由隧道连接挖煤点组成的无向图。
为安全起见,希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。
于是矿主决定在某些挖煤点设立救援出口,使得无论哪一个挖煤点坍塌之后,其他挖煤点的工人都有一条道路通向救援出口。
请写一个程序,用来计算至少需要设置几个救援出口,以及不同最少救援出口的设置方案总数。
输入格式
输入文件有若干组数据,每组数据的第一行是一个正整数 N,表示工地的隧道数。
接下来的 N 行每行是用空格隔开的两个整数 S 和 T(S≠T),表示挖煤点 S 与挖煤点 T 由隧道直接连接。
注意,每组数据的挖煤点的编号为 1∼Max,其中 Max 表示由隧道连接的挖煤点中,编号最大的挖煤点的编号,可能存在没有被隧道连接的挖煤点。
输入数据以 0 结尾。
输出格式
每组数据输出结果占一行。
其中第 i 行以 Case i: 开始(注意大小写,Case 与 i 之间有空格,i 与 : 之间无空格,: 之后有空格)。
其后是用空格隔开的两个正整数,第一个正整数表示对于第 i 组输入数据至少需要设置几个救援出口,第二个正整数表示对于第 i 组输入数据不同最少救援出口的设置方案总数。
输入数据保证答案小于 2^64 ,输出格式参照以下输入输出样例。
数据范围
1≤N≤500,
1≤Max≤1000
样例
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
Case 1: 2 4
Case 2: 4 1
算法1
(tarjan缩点 + 求点双连通分量) $O(n + m)$
题目不一定说图是连通的,可能有孤立点。
本题思路:
1、首先统计所有的连通分量
由于每个连通分量是独立的,因此我们安排救援出口只需要一个一个连通块去考虑。
2、缩点,将连通分量都缩成一个点,然后点与点之间如果有割点的话,每个点向割点连一条边
3、对于缩点后的图,分类讨论
res 表示 救援出口数量,num 表示 方案数 用乘法原理,因为每个连通分量之间的独立的
如果 点的度数为 0,那么要安排两个出口 res +=2,同时num *= dcc[i].size() * (dcc[i].size() - 1) / 2;
当然要特判如果说连通块中只有一个点那么res ++ 即可
如果点的度数为 1,那么要安排一个出口,证明无论坍塌哪个点都能成功逃脱
如果点的度数为 2,不需要安排出口。
点的度数其实就是 一个连通分量与割点相连的数量
为什么这样安排,救援出口数量就是最少的?
证明如下:
直观感受上,每个连通分量必须要两个出口,因为如果其中一个出口坍塌了,那么工人们将会被困死在里面
但是如果我们考虑连通分量之间有割点相连,如果割点坍塌了,那么每个连通分量只需要安排一个出口。
将图缩点后,我们可以将每个连通分量按度数来划分不同的情况。
1、连通分量度数为 0,孤立的连通分量内部必须安排两个出口,两个出口可以任意选,假设有连通分量中有cnt个点,那么从cnt个点中任选2个点。cnt * (cnt - 1) / 2
2、连通分量度数为 1,说明与一个割点相连,如果割点坍塌了,那么要安排一个出口在连通分量内部,如果连通分量内部的某个点坍塌了,那么由于有割点的存在,这个连通分量中的工人可以通过割点转移到别的连通分量逃离。每个连通分量都要安排一个出口,由于一个割点至少会属于两个点双连通分量中,因此除了割点以外还有cnt - 1个出口选择。
3、连通分量度数大于 2,不需要安排出口,因为至少和两个割点相连,意味着无论坍塌哪个?都能够直接或间接地逃离。
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <cstring>
#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;
bool cut[N]; // 判断是否为割点
vector<int> dcc[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); // y != j 因为所有与割点相连的连通分量都需要加入一个割点,因此我们循环条件到 y != j
dcc[dcc_cnt].push_back(u); // 割点u不出栈,但是会加入到相应的连通分量中
}
}else low[u] = min(low[u],dfn[j]);
}
}
int main()
{
int T = 1;
while(cin >> m,m){
// 每组数据的所有初始化
memset(h, -1, sizeof h);
memset(dfn,0,sizeof dfn);
memset(cut,0,sizeof cut);
for(int i = 1;i<=dcc_cnt;i++) dcc[i].clear();
idx = timestamp = n = top = dcc_cnt = 0;
while(m -- ){
int a,b;
cin >> a >> b;
n = max(n,a),n = max(n,b); // 记录最大编号max
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;
}