题目描述
煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见，希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设立救援出口，使得无论哪一个挖煤点坍塌之后，其他挖煤点的工人都有一条道路通向救援出口。
请写一个程序，用来计算至少需要设置几个救援出口，以及不同最少救援出口的设置方案总数。
题解
这道题我们首先进行(tarjan)求出割点，然后(dfs)扫一下所有的连通块。
我们对每一个连通块中的割点数目进行讨论：
如果没有割点，我们需要建造两个救援出口，而方案数为(C(n,2) = n * (n - 1) / 2)。
如果只有一个割点，那么我们只要建造一个救援出口就好了，方案数为(n)。
如果有两个或两个以上个割点，那么割点分成的部分就可以互通，所以就不需要建造救援出口了。
#include <iostream>
#include <cstdio>
#include <cstring>
#define ll long long
using namespace std;
const int N = 605;
int n, m, dfn[N], cut[N], num, low[N], head[N], tot, vis[N], rt, flag, sum, cnt1, cnt2, id, now;
ll ans;
struct node{int to, nex;}a[N << 1];
inline int read()
{
int x = 0, f = 1; char ch = getchar();
while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
while(ch >= '0' && ch <= '9') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
return x * f;
}
void add(int x, int y) {a[++ tot].to = y; a[tot].nex = head[x]; head[x] = tot;}
void tarjan(int x, int fa)
{
dfn[x] = low[x] = ++ num;
for(int i = head[x]; i; i = a[i].nex)
{
int y = a[i].to;
if(!dfn[y])
{
tarjan(y, x); low[x] = min(low[x], low[y]);
if(low[y] >= dfn[x])
{
if(x != rt) cut[x] = 1;
else flag ++;
}
}
else if(y != fa) low[x] = min(low[x], dfn[y]);
}
if(x == rt && flag > 1) cut[x] = 1;
}
void dfs(int x)
{
cnt1 ++; vis[x] = id;
for(int i = head[x]; i; i = a[i].nex)
{
int y = a[i].to;
if(cut[y] && vis[y] != id) {cnt2 ++; vis[y] = id;}
if(!vis[y]) dfs(y);
}
}
void work()
{
while((m = read()))
{
for(int i = 1; i <= n; i ++) dfn[i] = head[i] = cut[i] = vis[i] = 0;
num = sum = id = tot = n = 0; ans = 1;//n
for(int i = 1, x, y; i <= m; i ++) {x = read(); y = read(); add(x, y); add(y, x); n = max(n, max(x, y));}
for(int i = 1; i <= n; i ++) if(!dfn[i]) rt = i, flag = 0, tarjan(i, 0);
for(int i = 1; i <= n; i ++)
{
if(cut[i] || vis[i]) continue;
++ id; cnt1 = cnt2 = 0; dfs(i);
if(cnt2 == 0) sum += 2, ans = ans * (cnt1 - 1) * cnt1 / 2;
else if(cnt2 == 1) sum += 1, ans = ans * cnt1;
}
printf("Case %d: %d %lld
", ++ now, sum, ans);
}
}
int main() {return work(), 0;}