题解 P3225 【[HNOI2012]矿场搭建】

· · 题解

这里是唯一的一个Tarjan后不用再DFS的题解。

思路：无向图跑Tarjan时就跑出所有割点和DCC（点双连通分量）。

  1. 如果这个DCC包含了1个以上的割点，那么无论拿一个割点被堵，都可以通过其他割点逃向其他救生点，没有贡献答案。

  2. 如果这个DCC只有1个割点，如果割点被堵，就在DCC内设立一个逃生点，如果逃生点被堵，就从割点出去。贡献为1，方案数为size[i]-1（除去割点本身）。

  3. 如果这个DCC没有割点。就要用两个逃生点互保。贡献为2，方案数为size[i]*(size[i]-1)/2。所有方案数乘起来就是答案。

跑Tarjan时，类似有向图的做法维护一个栈。如果有LOW[y]>=DFN[x]的情况，就把从y到栈顶的部分一起弹出，他们和x构成了一个DCC（详见代码）。然后统一计算答案。

为什么不能在Tarjan时计算答案：

当你确定一个点双连通分量后，里面的所有点哪些是割点，哪些不是割点还没算完，所以是错的。要等Tarjan完后再算答案。

#include <bits/stdc++.h>
#define MAX (1000 + 7)
#define add push_back
using namespace std;

int T,N,M,K,cnt,ans1,c[MAX],LOW[MAX],DFN[MAX];//c保存是否为割点 
long long ans2;

vector <int> L[MAX],DCC[MAX];//DCC数组保存每一个DCC 
stack <int> S;

void Tarjan(int x)
{
    int fa = 0; S.push(x);
    LOW[x] = DFN[x] = ++cnt;
    for (int p = 0; p < L[x].size(); p++)
    {
        const int y = L[x][p];
        if (!DFN[y])
        {
            Tarjan(y);
            LOW[x] = min(LOW[x], LOW[y]);
            if (LOW[y] >= DFN[x])
            {
                fa++; K++;
                if (x!=1 || fa>1) c[x] = 1;
                DCC[K].add(x);
                int z = 0;
                do{//Tarjan时弹栈并直接求出DCC 
                    z = S.top(); S.pop();
                    DCC[K].add(z);
                }while (z != y);
            }
        }
        else LOW[x] = min(LOW[x], DFN[y]);
    }
}

int main()
{
    while (scanf("%d", &M) && M)
    {
        S = stack <int> ();
        for (int i = 1; i <= N; i++)
            L[i].clear();
        for (int i = 1; i <= K; i++)
            DCC[i].clear();
        N = K = ans1 = cnt = 0; ans2 = 1;
        memset(c, 0, sizeof c);
        memset(LOW, 0, sizeof LOW);
        memset(DFN, 0, sizeof DFN);

        for (int i = 1, x = 0, y = 0; i <= M; i++)
        {
            scanf("%d%d", &x, &y);
            L[x].add(y); L[y].add(x);
            N = max(N, max(x,y));
        }
        Tarjan(1);
        for (int i = 1; i <= K; i++)
        {//统一对每一个DCC计算答案。 
            int v1 = DCC[i].size(), v2 = 0;
            //size()即该DCC的点个数，v2计算割点个数 
            for (int p = 0; p < v1; p++)
                v2 += c[DCC[i][p]];
            if (v2 == 1) ans1++, ans2 *= v1 - 1;
            if (v2 == 0) ans1 += 2, ans2 *= v1 * (v1-1) / 2;
        }
        printf("Case %d: %d %lld\n", ++T, ans1, ans2);
    }
}