矿场搭建-点双

洛谷 P3225 [HNOI2012]矿场搭建

思路

满足无论哪个挖煤点坍塌之后，其他挖煤点的工人都有一条道路通向救援出口即说明出口与点双存在一定的对应关系；

可以认为，同一个连通块内的不用点双由一个个割点“切”开的，也就是说，一个点双内会有若干个（含0）割点，我们可以对此进行分类讨论；

假设当前点双总结点数为 c ，割点数为 d ；

1. 若 c=0 ，则需要一个出口，即在唯一的节点上；
2. 若 d=0，则需要两个出口进行互保，不同的方案数有 $c(c-1)/2$ 种；
3. 若 d=1，则需要一个出口，在非割点，即若割点坍塌，可从出口逃离，若出口坍塌，可从割点到其他点双逃离，不同方案有 $c-1$ 种；
4. 若 d>=2，则不需要出口，无论哪个点坍塌，都可以从现存的割点逃离；

在具体实现上，我们可以在处理割点的同时处理出来点双，对于每个点双进行统计，最终维护出答案；

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
const int M = 1e8;
int vis[N];
int ctp[N];
stack<int> s;       //dfs栈
vector<int> rod[N]; //存路
int dfn[N], dc = 1; //dfs存储dfs入序，dc用于分配dfs序
int low[N];         //low存储节点下子树通过返祖边所连接的最小dfs序
int cut[N];
vector<int> scc[N];
int sc = 1; //scc存储每个双连通分量内的元素，sc分配双连通分量编号
void dfs(int u, int r)
{
    s.push(u);
    cut[u]=(u==r)?0:1;
    low[u] = dfn[u] = dc++;
    if (u == r && rod[u].empty())
    {
        int now = s.top();
        s.pop();
        scc[sc].push_back(now);
        sc++;
    }
    for (int j = 0; j < rod[u].size(); j++)
    {
        int to = rod[u][j];
        if (!dfn[to])
        {
            dfs(to, r);
            low[u] = min(low[u], low[to]);
            if (low[to] >= dfn[u])
            {
                int now;
                do
                {
                    now = s.top();
                    s.pop();
                    scc[sc].push_back(now);
                } while (now != to);
                scc[sc].push_back(u);
                sc++;
                cut[u]++;
            }
        }
        else
        {
            low[u] = min(low[u], dfn[to]);
        }
    }
}

int main()
{
    int n, m, a, b,cc=1;
    while (cin >> m&&m)
    {
        int mx=0;
        dc=1,sc=1;
        for (int i = 1; i <= m; i++)
        {
            scanf("%d%d", &a, &b);
            vis[a]=1,vis[b]=1;
            mx=max(mx,a);
            mx=max(mx,b);
            rod[a].push_back(b);
            rod[b].push_back(a);
        }
        int mn=0;//出口数
        ll cmn=1;//方案数
        for (int i = 1; i <= mx; i++)
        {
            if (vis[i]&&!dfn[i])
            {
                dfs(i, i);
            }
        }
        for(int i=1;i<sc;i++)
        {
            int cnt=0;//统计割点
            if(scc[i].size()==1)
            {
                mn++;
            }
            else
            {
                for(int j=0;j<scc[i].size();j++)
                {
                    if(cut[scc[i][j]]>=2)cnt++;
                }
                if(cnt==0)
                {
                    mn+=2;
                    cmn*=(1ll*scc[i].size()-1)*1ll*scc[i].size()/2;
                }
                else if(cnt==1)
                {
                    mn++;
                    cmn*=1ll*(scc[i].size()-1);
                }
            }
            scc[i].clear();
        }
        for(int i=1;i<=mx;i++)//初始化
        {
            if(vis[i])
            {
                vis[i]=0;
                ctp[i]=0;
                rod[i].clear();
                dfn[i]=low[i]=0;
            }
        }
        printf("Case %d: %d %lld\n",cc++,mn,cmn);
    }
    return 0;
}

ED

\