【BZOJ】2730: [HNOI2012]矿场搭建【Tarjan找割点】【分联通块割点个数】

2730: [HNOI2012]矿场搭建

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 3230 Solved: 1540
[Submit][Status][Discuss]

Description

煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见，希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设立救援出口，使得无论哪一个挖煤点坍塌之后，其他挖煤点的工人都有一条道路通向救援出口。请写一个程序，用来计算至少需要设置几个救援出口，以及不同最少救援出口的设置方案总数。

Input

输入文件有若干组数据，每组数据的第一行是一个正整数 N（N≤500），表示工地的隧道数，接下来的 N 行每行是用空格隔开的两个整数 S 和 T，表示挖 S 与挖煤点 T 由隧道直接连接。输入数据以 0 结尾。

Output

输入文件中有多少组数据，输出文件 output.txt 中就有多少行。每行对应一组输入数据的结果。其中第 i 行以 Case i: 开始（注意大小写，Case 与 i 之间有空格，i 与:之间无空格，: 之后有空格），其后是用空格隔开的两个正整数，第一个正整数表示对于第 i 组输入数据至少需要设置几个救援出口，第二个正整数表示对于第 i 组输入数据不同最少救援出口的设置方案总数。输入数据保证答案小于 2^64。输出格式参照以下输入输出样例。

Sample Input

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

Sample Output

Case 1: 2 4
Case 2: 4 1

HINT

Case 1 的四组解分别是(2,4),(3,4),(4,5),(4,6)；

Case 2 的一组解为(4,5,6,7)。

Solution

可以发现要找的特殊点的数量和图中割点有关。因为割点会把一个联通块分离成几块，导致中间断开，此时肯定需要增加安放的特殊点。

当把割点删去后分离成多个点双联通分量。

此时对每个点双进行讨论：

如果点双中与0个割点相邻，那么需要在点双中新增两个特殊点，防止其中一个特殊点挂了。

如果点双中与1个割点相邻，那么需要在点双中新增一个特殊点，为这个割点提供备用。

如果点双中与2个割点相邻，那么不需要增加特殊点，一个割点挂了可以走另一个割点离开。

然后就可以用乘法原理算出方案数了。

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

int n, m;

struct Node {
    int u, v, nex;
} Edge[100005];

int stot, h[505];
void add(int u, int v) {
    Edge[++stot] = (Node) {u, v, h[u]};
    h[u] = stot;
}

int dfn[505], low[505], idc, stk[505], tp, cut[505];
void Tarjan(int u, int fa) {
    dfn[u] = low[u] = ++ idc;
    stk[++tp] = u;
    int son = 0;
    for(int i = h[u]; i; i = Edge[i].nex) {
        int v = Edge[i].v;
        if(i == (fa ^ 1))    continue;
        if(!dfn[v]) {
            son ++;
            Tarjan(v, i);
            low[u] = min(low[u], low[v]);
            if(low[v] >= dfn[u]) cut[u] = 1;
        } else    low[u] = min(low[u], dfn[v]);
    }
    if(fa == 0 && son == 1)    cut[u] = 0;
}

int siz, cut_num, cnt, color[505];
void dfs(int u) {
    color[u] = cnt;
    if(cut[u])    return ;
    siz ++;
    for(int i = h[u]; i; i = Edge[i].nex) {
        int v = Edge[i].v; 
        if(cut[v] && color[v] != cnt) {
            cut_num ++; color[v] = cnt;
        }
        if(!color[v])    dfs(v);
    }
}

int main() {
    int ti = 0;
    while(~scanf("%d", &m)) {
        if(m == 0)    break;
        n = 0;
        stot = 1;    memset(h, 0, sizeof(h));
        cnt = 0;    tp = 0;        idc = 0;
        memset(dfn, 0, sizeof(dfn));
        memset(low, 0, sizeof(low));
        memset(color, 0, sizeof(color));
        memset(cut, 0, sizeof(cut));
        for(int i = 1; i <= m; i ++) {
            int u, v;
            scanf("%d%d", &u, &v);
            add(u, v);    add(v, u);
            n = max(max(n, v), u);
        }
        for(int i = 1; i <= n; i ++)    if(!dfn[i])    Tarjan(i, 0);
        LL ans1 = 0, ans2 = 1;
        for(int i = 1; i <= n; i ++) {
            if(!cut[i] && !color[i]) {
                cnt ++;    siz = 0, cut_num = 0;    dfs(i);
                if(cut_num == 0) { ans1 += 2; ans2 *= 1ll * (siz - 1) * siz / 2;}
                if(cut_num == 1) { ans1 += 1; ans2 *= siz;}
            }
        }
        printf("Case %d: %lld %lld
", ++ti, ans1, ans2);
    }
    return 0;
}