P3225 矿场搭建

问题

P3225 [HNOI2012] 矿场搭建
矿场由若干挖煤点和双向隧道组成，矿主可以选择一些挖煤点设置救援出口。需要保证任意一个挖煤点坍塌后，其他挖煤点的工人仍能沿隧道到达至少一个没有坍塌的出口；要求计算最少需要设置多少个出口，以及达到最少数量时共有多少种选点方案。

每组输入给出不超过 $500$ 条边，实际顶点编号不超过 $1000$，方案数保证小于 $2^{64}$。

原图保证连通，而事故只会破坏一个挖煤点。由于破坏对象是点，关键结构自然落在割点和点双连通分量上。

接着我们在每个点双里找存在几个割点：

1. 若一个点双中恰好包含一个割点，那么这个割点是该点双与其余部分连接的唯一接口。它坍塌后，该点双中的非割点无法前往其他点双，因此必须任选一个非割点设置出口；若可选点数为 $c$，方案数就乘上 $c$。

2. 若一个点双包含至少两个割点，删除任意一个割点后，它仍能经其他割点通向其他点双，因此无需在这里额外设置出口。

3. 若一个点双不含割点，由于原图连通，说明整张图本身就是一个点双。此时只设置一个出口会存在“出口自身坍塌”的情况，因此必须任选两个不同顶点，方案数为 $\displaystyle \binom c2$。

Tarjan 与统计总共线性遍历当前图，时间复杂度为 $O(V+E)$，空间复杂度为 $O(V+E)$。方案数使用 unsigned long long，与题目给出的 $2^{64}$ 上界约定对应。

▶

P3225 矿场搭建

struct Edge { int id, v; ll w; };
vector<Edge> adj[maxn];
vector<int> comp[maxn];

int dfn[maxn], low[maxn], timer;
int stk[maxn], top;

bool cut[maxn];
int vcnt;

void add_edge( int u, int v, ll w, int id ) {
    adj[u].push_back({ id, v, w });
    adj[v].push_back({ id, u, w });
}

void tarjan( int u, int in_edge ) {
    dfn[u] = low[u] = ++ timer;
    stk[++ top] = u;
    int child = 0;
    for( auto [id, v, w] : adj[u] ) {
        if( !dfn[v] ) {
            child ++;
            tarjan( v, id );
            low[u] = min( low[u], low[v] );
            if( low[v] >= dfn[u] ) {
                if( in_edge || child >= 2 ) {
                    cut[u] = true;
                }
                vcnt ++;
                comp[vcnt].push_back( u );
                int x;
                do {
                    x = stk[top --];
                    comp[vcnt].push_back( x );
                } while( x != v );
            }
        } else if( id != in_edge ) {
            low[u] = min( low[u], dfn[v] );
        }
    }
    if( !in_edge && child == 0 ) {
        ++ vcnt;
        comp[vcnt].push_back( u );
        -- top;
    }
}

bool exist[maxn];
vector<int> ver;
int Case = 1;

void solve( int edges ) {
    if( edges == 0 ) return;
    
    ver.clear( );
    timer = top = vcnt = 0;
    for( int i = 1; i < maxn; ++ i ) {
        adj[i].clear( );
        comp[i].clear( );
        dfn[i] = low[i] = 0;
        cut[i] = exist[i] = 0;
    }

    for( int i = 1; i <= edges; ++ i ) {
        int u = read( ), v = read( );
        add_edge( u, v, 0, i );
        if( !exist[u] ) {
            exist[u] = 1;
            ver.push_back( u );
        }
        if( !exist[v] ) {
            exist[v] = 1;
            ver.push_back( v );
        }
    }

    for( int u : ver ) {
        if( !dfn[u] ) tarjan( u, 0 ), top = 0;
    }

    int ans = 0;
    ull ways = 1;

    for( int u = 1; u <= vcnt; ++ u ) {
        int ccnt = 0; // 割点数量
        int ocnt = 0; // 非割点数量
        for( int v : comp[u] ) {
            if( cut[v] ) ++ ccnt;
            else ++ ocnt;
        }

        if( ccnt == 0 ) {
            ans += 2;
            ways *= 1ull * ocnt * ( ocnt - 1 ) / 2;
        }
        else if( ccnt == 1 ) {
            ans += 1;
            ways *= ocnt;
        }
    }
    printf( "Case %d: %d %llu\n", Case++, ans, ways );
}

记录

• 归属：点双连通分量、割点；

• 新增：答案不是割点数量，而是块割结构中叶子点双的需求；恰含一个割点的点双选一个非割点，整图无割点时任选两个顶点。

• 分类：待定