P3225 [HNOI2012] 矿场搭建 题解

· · 题解

提供一种圆方树做法。

首先先建出一颗圆方树，考虑对于一个圆点，它坍塌后会产生的影响。

若该点为一个叶子节点，即不为一个割点，则不会对原图的连通性产生影响。

若该点为一个割点，则其的父亲节点所在连通块，和它儿子节点所在的连通块会分离。

此时分离出来的每一个连通块，都应有一个救援出口。

我们暂且不考虑其父亲连通块的状态。

设 f_i 表示点 i 坍塌后，其子树内最少的救援出口数量，设 g_i 为方案数。

则有，对于圆点：

f_i=\sum\limits_{v\in son_i} \max(f_v,1) g_i=\prod\limits_{v\in son_I} \begin{cases}g_v&f_v\ne0\\size_v&f_v=0\end{cases}

对于方点：

f_i=\sum\limits_{v\in son_i}f_v g_i=\prod\limits_{v\in son_I} g_v

现在考虑其父亲节点所在连通块的状态。

我们不妨令一个割点为根，那么其肯定至少有两个儿子，并且每个儿子的子树中都必定有一个救援出口。

所以，当你断掉一个割点后，其父亲节点所在的连通块，即为根所在的连通块，转移到最后，一定会存在一个救援通道，所以不需要单独考虑。

最终的答案即为 f_{root} 和 g_{root}。

注意需要特判整张图就是一个点双的情况。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=5e5+5;
vector<int> e[maxn],g[maxn];
int n,dfn[maxn],low[maxn],idx,dcc,m,d[maxn];
stack<int> q;
void tarjan(int x,int fa)
{
    dfn[x]=low[x]=++idx;
    q.push(x);
    for(auto v:e[x])
    {
        if(v==fa)
            continue;
        if(!dfn[v])
        {
            tarjan(v,x);
            low[x]=min(low[x],low[v]);
            if(low[v]>=dfn[x])
            {
                ++dcc;
                int ls=0;
                do
                {
                    g[dcc].push_back(ls=q.top()),g[q.top()].push_back(dcc),++d[q.top()],q.pop();
                }while(ls!=v);
                ++d[x];
                g[dcc].push_back(x),g[x].push_back(dcc); 
            }
        }
        else
            low[x]=min(low[x],dfn[v]);
    }
}
int f[maxn],G[maxn],siz[maxn];
void dfs(int x,int fa)
{
    G[x]=1;
    siz[x]=x<=n;
    for(auto v:g[x])
    {
        if(v==fa)
            continue;
        dfs(v,x);
        siz[x]+=siz[v];
        if(x<=n)
            f[x]+=max(f[v],1ll),G[x]*=(f[v]==0?siz[v]:G[v]);
        else
            f[x]+=f[v],G[x]*=G[v];
    }
}
signed main()
{
    int T=0;
    while(cin>>m)
    {
        ++T;
        if(m==0)
            break;
        int k=0;
        memset(d,0,sizeof d);
        memset(f,0,sizeof f);
        memset(g,0,sizeof G);
        memset(low,0,sizeof low);
        memset(dfn,0,sizeof dfn);
        memset(d,0,sizeof d);
        n=0;
        while(!q.empty())
            q.pop();
        idx=0;
        for(int i=1;i<=m;i++)
        {
            int x,y;
            cin>>x>>y;
            n=max(n,max(x,y));
            k=x;
            e[x].push_back(y),e[y].push_back(x);
        }
        dcc=n;
        tarjan(k,k); 
        for(int i=1;i<=n;i++)
            if(d[i]>=2)
                k=i;
        dfs(k,k);
        if(dcc==n+1) 
            cout<<"Case "<<T<<": "<<2<<' '<<n*(n-1)/2<<endl; 
        else
            cout<<"Case "<<T<<": "<<f[k]<<' '<<G[k]<<endl;
        for(int i=1;i<=dcc;i++)
            g[i].clear(),e[i].clear();
    }
    return 0;
}