🪴 Edwin Aze's Blog

最近文章

最近笔记

矿场搭建

8分钟阅读

396. 矿场搭建 - AcWing题库 煤矿工地可以看成是由隧道连接挖煤点组成的无向图。

为安全起见，希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。

于是矿主决定在某些挖煤点设立救援出口，使得无论哪一个挖煤点坍塌之后，其他挖煤点的工人都有一条道路通向救援出口。

请写一个程序，用来计算至少需要设置几个救援出口，以及不同最少救援出口的设置方案总数。

输入格式

输入文件有若干组数据，每组数据的第一行是一个正整数 ，表示工地的隧道数。

接下来的 行每行是用空格隔开的两个整数 和 （），表示挖煤点 与挖煤点 由隧道直接连接。

注意，每组数据的挖煤点的编号为 ，其中 表示由隧道连接的挖煤点中，编号最大的挖煤点的编号，可能存在没有被隧道连接的挖煤点。

输入数据以 结尾。

输出格式

每组数据输出结果占一行。

其中第 行以 Case i: 开始（注意大小写，Case 与 i 之间有空格，i 与 : 之间无空格，: 之后有空格）。

其后是用空格隔开的两个正整数，第一个正整数表示对于第 组输入数据至少需要设置几个救援出口，第二个正整数表示对于第 组输入数据不同最少救援出口的设置方案总数。

输入数据保证答案小于 ，输出格式参照以下输入输出样例。

数据范围

，

输入样例：

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

输出样例：

Case 1: 2 4
Case 2: 4 1

思路

给一个无向图, 求当有一个点被删除时, 其他所有点仍存在路径通向设立有 ”救援出口“ 的点, 求 ”救援出口“ 最小设立多少个, 才能满足要求。

对于连通性问题, 先用连通分量的角度来思考, 把整个图分为 点双连通分量 和 割点。若坍塌点在 点双连通分量内, 有两种情况：

  • 坍塌点刚好是设立出口的点
  • 坍塌点不是设立出口的点 为了保险起见, 至少要设定两个不同的出口, 才能保证一个出口坍塌时, 其他人可以从另一个出口逃脱。因此, 在双连通分量中需要设定两个出口。

点双连通分量缩点如图： 缩完点之后, 每一个连通分量根据相连的割点数分为以下情况：

  • 无割点, 即度为0的时候, 总的方案数为 , 即
  • 有一个割点, 即度为1的时候, 若断的是割点, 则割点所在的两个连通分量将无法互相到达, 故需要两个分量各安置一个出口, 总的方案数为
  • 有2个及以上割点, 即度大于等于2时, 无论是断其中一个割点, 还是断内部点, 都能到达度为1的点（会设置一个出口）从而逃脱。

代码流程：

  1. tarjan求点双连通分量, 且需要缩点
  2. 读入图后, 枚举所有点编号, 若还未搜过就以该点为根进行tarjan
  3. tarjan中先标记时间戳 , 并将当前点加入到 中
  4. 枚举子节点, 若没更新过 就递归更新
    1. 同时更新当前点的
    2. 若满足 , 说明 点无法到达 比更高的节点, 那么 就可能是一个割点, 将当前割点数量
    3. 若此时 （有两个以上的子树）或者 （ 不是根节点）, 就确定 是一个割点, 将 即可
    4. 然后将 所在分量缩点, 直到 出栈（保留 在栈中）
    5. 最后还要把 也加到连通块里
  5. 若更新过就更新
  6. 最后枚举所有连通块, 根据割点数量累加得出答案

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <vector>
using namespace std;
typedef long long LL;
const int N = 1010, M = 550;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int stk[N], top;
vector<int> dcc[N];
bool cut[N];
int dcc_cnt;
int n,m, root;
 
void add(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx++;}
 
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(dfn[u] <= low[j])
            {
                cnt++;
                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 kase = 0;
    while(cin >> m, m)
    {
        memset(h, -1, sizeof h);
        memset(dfn, 0, sizeof dfn);
        memset(low, 0, sizeof low);
        memset(cut, 0, sizeof cut);
        idx = timestamp = dcc_cnt = top = 0;
        n = 0;
        
        for(int i = 0; i < m; i++)
        {
            int a, b;
            cin >> a >> b;
            add(a,b), add(b,a);
            n = max(a, max(n,b));
        }
        for(int i = 0; i <= n; i++) dcc[i].clear();
        for(root = 1; root <= n; root++)
            if(!dfn[root])
                tarjan(root);
                
        int res = 0;
        LL num = 1;
        for(int i = 1; i <= dcc_cnt; i++)
        {
            int cnt = 0, sz = dcc[i].size();
            for(int j = 0; j < sz; j++)
                if(cut[dcc[i][j]]) cnt++;
            if(sz == 1) sz++,cnt=1;
            if(cnt == 0) res += 2, num *= sz*(sz-1)/2;
            else if(cnt == 1) res += 1, num *= sz - 1;
            //cout << i << " " << res << endl;
        }
        cout << "Case " << ++kase << ": " << res << " " << num << endl;
    }
    return 0;
}

反向链接