526互联

the solution of Mining Your Own Business

发布时间 2023-09-25 13:26:06作者: carp_oier

the description of problem

（我看的是 PDF 里面的原题所以这里描述会和题目不一样，但是大意一致）

给定一个未必连通的无向图，问最少在几个点设置出口，可以保证任意一个点坍塌后，工人们仍然可以从出口逃生，同时问设置最少出口的方案数量。

thoughts & solution

我们可以知道每个连通块之间是相互独立的，对于每个连通块间的答案，是互不影响的，所以说每个连通块之间的答案是要靠乘法原理维护。

（下面都用 res 来记录我们需要设置的出口数量，num 来表示我们总共的方案数）

这个时候我们考虑每个连通块：

  1. 如果这个连通块中没有割点，这个时候我们只需要在这个连通块内部随意放置两个出口就可以保证每个点都能到达出口。我们还需要分类讨论:

    • 如果这个连通块内只有一个点，我们的答案就将变成

      \[res++ \]

    • 我们这个时候记录答案就是（记这个连通块内部有 cnt 个点）

      \[res += 2, num *= C_{cnt} ^ {2} \]

  2. 如果这个连通块中只有一个割点，我们需要对它进行一个缩点的操作，这个时候，我们的一个割点会一分为二，分别到它这个割点所连接的两个连通分量中，这个时候我们只需要保证里面有一个出口就行了，方案数则是这个左右两个分量中个自得数量（记为 cnt）

\[res ++, num *= cnt - 1 \]

  1. 如果这个连通块有两个或两个以上得割点，我们这个时候则可以证明它一定能去往别得连通块，所以说不会对结果造成贡献。证明放在后面。

Proof

  1. 如果在割点坍塌，在缩完点之后必定是一棵树，而且我们在每一个之前只有一个割点的连通图里面放置了一个出口，所以，在这棵树的最下面必定会有叶子节点，这个叶子节点就会救活这棵树。

  2. 如果是连接了一个割点的 V-DCC 坍塌某一个点，我们在删除这个坍塌的点之后，我们这个图还是连通的，而且因为这个图上面还有一个割点，我们就可以通过这个割点走向另外一个安全的出口。

  3. 如果是连接了两个割点的 V-DCC 坍塌了某一个点，我们同样可以让这个图里面的点去到其他出口。

综上，证毕

CODE TIME

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rl register ll

const ll N = 5e4 + 10, M = 1e5 + 10;

ll n, m;

ll tot, ne[M], e[M], h[N];

ll dfn[N], low[N], timestamp;

ll stk[N], top, dcc_cnt, root;

vector<ll> dcc[N];

bool cut[N];

inline void add(ll a, ll b)
{
    ne[++tot] = h[a], h[a] = tot, e[tot] = b;
}

inline void tarjan(ll u)
{
    dfn[u] = low[u] = ++ timestamp;
    stk[ ++ top] = u;
    
    if(root == u && h[u] == -1)
    {
        dcc_cnt ++, dcc[dcc_cnt].push_back(u);
        return ;
    }

    ll cnt = 0;
    for(rl i=h[u]; ~i; i = ne[i])
    {
        ll v = e[i];
        if(!dfn[v]) 
        {
            tarjan(v), low[u] = min(low[u], low[v]);
            if(dfn[u] <= low[v])
            {
                cnt ++;
                if(u != root || cnt > 1) cut[u] = true;
                ++ dcc_cnt;
                ll ele;
                do {
                    ele = stk[top --];
                    dcc[dcc_cnt].push_back(ele);
                } while(ele != v);
                dcc[dcc_cnt].push_back(u);
            }
        }
        else low[u] = min(low[u], dfn[v]);
    }
}

int main()
{
    ll T = 1;
    while(cin >> m, m)
    {
        for(rl i=1; i <= dcc_cnt; ++ i) dcc[i].clear();
        tot = n = timestamp = top = dcc_cnt = 0;
        memset(h, -1, sizeof h), memset(dfn, 0, sizeof dfn), memset(cut, 0, sizeof cut);
        
        while(m -- )
        {
            ll a, b;
            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);
                
        ll res = 0, num = 1;
        
        for(rl i=1; i <= dcc_cnt; ++ i)
        {
            ll cnt = 0;
            for(rl j : dcc[i])
                if(cut[j]) 
                    cnt ++ ;
                
            if(cnt == 0) 
            {
                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 %lld: %lld %lld\n", T ++, res, num);
    }
    return 0;
}