矿场搭建

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 3805 字
多组数据，每组给N条隧道，求最少设几个救援出
一本通
例
正文

// 原题：https://oj.yecheng.tv/p/T1521
// 题意：多组数据，每组给 N 条隧道（无向边），求最少设几个救援出口及最少出口下的方案数，使任意挖煤点塌了以后其余点都能走到某个出口，读入以 0 结束。
// 思路：Tarjan 求点双连通分量，先记下每个点双的点集并算出所有割点，再按点双统计：挨着 0 个割点要 2 个出口（方案 C(s, 2)），挨着 1 个割点要 1 个出口（方案 s），挨着 2 个及以上割点不用出口。
// 1. 一个点双只要挨着两个割点，无论哪个塌了都能从另一个走出去，因此不必在它内部放出口。
// 2. 点号没有给上界，先把出现过的点号离散化再建图；各点双彼此独立，出口数相加、方案数相乘。
// 复杂度：O(V + E) 时间 / O(V + E) 空间
// 易错点：方案数要按「非割点个数」算而不是点双大小，割点自身塌掉就失效，不能当出口。
// 易错点：割点必须在整棵 DFS 树跑完之后再统一判定，边跑边统计会把根的第一个儿子所在的点双误判成没有割点。
#include <bits/stdc++.h>
using namespace std;
struct Edge{
    int u;
    int v;
};
vector<Edge> elist;
vector<vector<int> > adj;
vector<vector<int> > blocks;
vector<int> stk;
vector<int> dfn, low, iscut, markv;
int idx;
void tarjan(int u, int inId, int root){
    dfn[u] = low[u] = ++idx;
    int child = 0;
    for(int k = 0; k < (int)adj[u].size(); k++){
        int id = adj[u][k];
        if(id == inId) continue;
        int v = elist[id].u ^ elist[id].v ^ u;
        if(!dfn[v]){
            stk.push_back(id);
            child++;
            tarjan(v, id, root);
            low[u] = min(low[u], low[v]);
            if(low[v] >= dfn[u]){
                if(u != root) iscut[u] = true;
                vector<int> vs;
                while(true){
                    int x = stk.back();
                    stk.pop_back();
                    int a = elist[x].u;
                    int b = elist[x].v;
                    if(!markv[a]){
                        markv[a] = 1;
                        vs.push_back(a);
                    }
                    if(!markv[b]){
                        markv[b] = 1;
                        vs.push_back(b);
                    }
                    if(x == id) break;
                }
                for(int t = 0; t < (int)vs.size(); t++) markv[vs[t]] = 0;
                blocks.push_back(vs);
            }
        }
        else if(dfn[v] < dfn[u]){
            stk.push_back(id);
            low[u] = min(low[u], dfn[v]);
        }
    }
    if(u == root && child > 1) iscut[root] = true;
}
int main(){
    int N;
    int cas = 0;
    while(cin >> N){
        if(N == 0) break;
        cas++;
        vector<int> ua(N), ub(N);
        vector<int> ids;
        for(int i = 0; i < N; i++){
            cin >> ua[i] >> ub[i];
            ids.push_back(ua[i]);
            ids.push_back(ub[i]);
        }
        sort(ids.begin(), ids.end());
        ids.erase(unique(ids.begin(), ids.end()), ids.end());
        int V = (int)ids.size();
        elist.clear();
        adj.assign(V, vector<int>());
        for(int i = 0; i < N; i++){
            int a = (int)(lower_bound(ids.begin(), ids.end(), ua[i]) - ids.begin());
            int b = (int)(lower_bound(ids.begin(), ids.end(), ub[i]) - ids.begin());
            elist.push_back((Edge){a, b});
            adj[a].push_back(i);
            adj[b].push_back(i);
        }
        dfn.assign(V, 0);
        low.assign(V, 0);
        iscut.assign(V, 0);
        markv.assign(V, 0);
        blocks.clear();
        stk.clear();
        idx = 0;
        for(int i = 0; i < V; i++){
            if(!dfn[i]) tarjan(i, -1, i);
        }
        unsigned long long need = 0;
        unsigned long long ways = 1;
        for(int i = 0; i < (int)blocks.size(); i++){
            int cutnum = 0;
            for(int t = 0; t < (int)blocks[i].size(); t++){
                if(iscut[blocks[i][t]]) cutnum++;
            }
            int plain = (int)blocks[i].size() - cutnum;
            if(cutnum == 0){
                need += 2;
                ways *= (unsigned long long)plain * (plain - 1) / 2;
            }
            else if(cutnum == 1){
                need += 1;
                ways *= (unsigned long long)plain;
            }
        }
        cout << "Case " << cas << ": " << need << " " << ways << "\n";
    }
    return 0;
}
矿场搭建

正文

一本通·提高篇的其它内容
