AcWing 396 矿场搭建

题目传送门

一、解题思路

首先容易想到割点，因为删去割点后，分割出的两个或以上的点双联通分量中，每一个都至少要有一个救援出口。而且在最优方案里，割点上是不能够设置救援出口的。所以算法是显然的：用\(Tarjan\)求点双连通分量。

首先求出所有割点。

没有割点:那么这个点双联通分量中，至少要有两个救援出口，而且每个都可以被选择，这时的选择方案数是\(C_{size}^2\)种，即\(1/2*size*(size?1)\)种。

有割点:

如果某点双连通分量连接的割点只有一个，那么该双连通分量里必须设置一个救援出口，方案数是\(size\)。

如果某点双连通分量连接的割点有两个或以上，那么删去其中一个割点后，必然还剩下一些与之相连割点，这个时候只要剩下的割点连接的点双连通分量中有救援出口，它就可以利用它们的救援出口，因此这个点双连通分量中是不需要设置出口的。

在\(DFS\)求出点双连通分量时顺便求出连接的割点数即可。最后的方案数采用乘法原理处理。

二、完整代码

#include 
using namespace std;
typedef unsigned long long ULL;
const int N = 1010, M = 1010;
int n, m;
int dfn[N], low[N], timestamp; // tarjan算法求割点
int stk[N], top;               //栈
int dcc_cnt;
vector dcc[N]; //双连通分量
bool cut[N];        //哪些节点是割点
int root;
int h[N], e[M], ne[M], idx;
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
/*
本题思路十分简单，用tarjan跑出所有的v_DCC和割点.
1.若此分量内有割点>1，则无论哪一个被堵，连通性依旧。贡献为0
2.若割点==1，则在割点及分量内任意一点各建一个，ans*=DCC.size()-1。贡献为1
3.若割点==0，则任建两个，ans=DCC.size()(DCC.size()-1)/2。贡献为2

首先一遍tarjan找出割点，将图缩点，这些大点中如果有只包含一个割点的，那么如果这个割点被去掉，则这个大点与图不连通，所以这个大点内必须有一个出口；
而如果没有割点，需要建两个出口，以防止一个出口点被去掉；
方案数就是放出口的大点的size乘积；没有割点则方案数为C(m,2)；
注意自己记录点数。
*/
//无向图点双连通性  v?DCC
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 (low[j] >= dfn[u]) {
                cnt++;
                //记录割点u
                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);
                dcc[dcc_cnt].push_back(u);
            }
        } else
            low[u] = min(low[u], dfn[j]);
    }
}
int main() {
    int T = 1;
    while (cin >> m, m) { //多组测试数据
        //每次清除上次记录的dcc_cnt连通块中点的向量数组
        for (int i = 1; i <= dcc_cnt; i++) dcc[i].clear();
        // idx:全新建图
        // n:这题太讨厌了，n居然让我们自己取max计算出来，shit~
        // timestamp:tarjan用的时间戳序号
        // top:tarjan中stack用的变量
        // dcc_cnt:连通分量的个数
        idx = n = timestamp = top = dcc_cnt = 0;
        memset(h, -1, sizeof h);    //链表头，全新建图
        memset(dfn, 0, sizeof dfn); //每个节点的dfs序时间戳序号
        memset(cut, 0, sizeof cut); //清空割点数组

        int a, b;
        for (int i = 0; i < m; i++) {
            cin >> a >> b;
            n = max(n, a), n = max(n, b); //鄙视一下~
            add(a, b), add(b, a);
        }
        //因为可能不是全连通的，需要枚举每个节点，找出所有连通块
        for (root = 1; root <= n; root++)
            if (!dfn[root]) tarjan(root); //以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) { //如果没有割点
                //如果数量大于2，救援出口可以在dcc[i].size()中选择两个，不区分顺序
                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;
}