洛谷 P3225 [HNOI2012]矿场搭建 题解

· · 个人记录

思路

先求出所有点双连通分量，注意tarjan弹栈时要保留u，因为u有可能会被其它分量包含。

然后对每个分量单独分类讨论。

1. 分量内无割点，且分量点数大于1

任选两个点作为出口即可，因为坍塌后剩余部分仍然连通。

所以对个数的贡献是 2，对方案数的贡献是 C_{size}^2（size 是分量内的点数）。

2. 分量内无割点，且分量点数等于1

显然这个点一定要是出口，对个数的贡献是 1。

3. 分量内有一个割点

如果坍塌的点不是割点，那剩下的点可以和其它连通分量互通。

如果坍塌的点是割点，那剩下的点里至少要有一个出口。

所以任选除割点外一点作为出口即可，对个数的贡献是 1，对方案数的贡献是 size - 1。

4.分量内割点数量大于1

无论坍塌的是哪个点，该分量都会和其它分量连通，所以无需新增出口。

tips

根据加法原理和乘法原理，统计个数时用加法，统计方案数时用乘法。

存储方案数的变量要开 unsigned long long。

Code

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int N = 1005;
struct Edge{
    int to, nxt;
}g[N];
int h[N], idx;
int dfn[N], low[N], vist;
int sta[N], top;
vector<int> dcc[N];
int dcc_cnt, root;
bool cut[N];
void add(int a, int b)
{
    g[++idx].to = b, g[idx].nxt = h[a], h[a] = idx;
}
void tarjan(int u)
{
    dfn[u] = low[u] = ++vist;
    sta[++top] = u;
    if (u == root && !h[u])
    {
        dcc[++dcc_cnt].push_back(u);
        return;
    }
    int cnt = 0;
    for (int i = h[u]; i; i = g[i].nxt)
    {
        int j = g[i].to;
        if (!dfn[j])
        {
            tarjan(j);
            low[u] = min(low[u], low[j]);
            if (low[j] >= dfn[u])
            {
                cnt ++;
                if (u != root || cnt > 1)
                    cut[u] = true;
                dcc_cnt ++;
                int y;
                do {
                    y = sta[top--];
                    dcc[dcc_cnt].push_back(y);
                } while(y != j);
                dcc[dcc_cnt].push_back(u);
            }
        }
        else
            low[u] = min(low[u], dfn[j]);
    }
}
void init()
{
    memset(h, 0, sizeof h);
    memset(dfn, 0, sizeof dfn);
    idx = vist = top = 0;
    for (int i=1;i<=dcc_cnt;i++)
        dcc[i].clear();
    dcc_cnt = 0;
    memset(cut, false, N);
}
void work(int m)
{
    int n = 0;
    while (m--)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        n = max(n, max(a, b));
        add(a, b);
        add(b, a);
    }
    for (root=1;root<=n;root++)
        if (!dfn[root])
            tarjan(root);
    int ans = 0;
    unsigned long long sum = 1;
    for (int i=1;i<=dcc_cnt;i++)
    {
        int cnt = 0;
        for (int j : dcc[i])
            if (cut[j])
                cnt ++;
        if (cnt == 0)
        {
            if (dcc[i].size() > 1)
            {
                ans += 2;
                sum *= dcc[i].size() * (dcc[i].size() - 1) / 2;
            }
            else
                ans ++;
        }
        else if (cnt == 1)
        {
            ans ++;
            sum *= dcc[i].size() - 1;
        }
    }
    printf("%d %llu\n", ans, sum);
}
int main()
{
    for (int T=1;;T++)
    {
        int m;
        scanf("%d", &m);
        if (m == 0)
            return 0;
        init();
        printf("Case %d: ", T);
        work(m);
    }
    return 0;
}