题解归档 - NC20099

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：NC20099
• 本地来源：problems/NC20099/idea.md
• 原始标题：NC20099 [HNOI2012] 矿场搭建

思路

NC20099 [HNOI2012] 矿场搭建

题意

• 无向图，在若干点放救援出口；任意单点坍塌后，剩余每个连通块内都要有出口。
• 求最少出口数与方案数（多测，N 为边数，N=0 结束）。

思路

• Tarjan 求割点 + 点双连通分量。

• 每个点双内割点数 c：

  • c>=2：不额外放出口；
  • c==1：放 1 个（不能放割点上），方案乘 |DCC|-1；
  • c==0：整图一个点双，放 2 个，方案乘 C(|DCC|,2)。

代码

来源：problems/NC20099/solution.cpp

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;
const ll maxn=1010;
vector<ll>ss[maxn+5];
vector<ll>cccc[maxn+5];
ll dfn[maxn+5],low[maxn+5],st[maxn+5],top,timer,mx,cccc_cnt;
bool cut[maxn+5];
void tarjan(ll u,ll root){
    ll i,v,sz,cnt;
    dfn[u]=++timer;
    low[u]=timer;
    st[++top]=u;
    sz=ss[u].size();
    if(u==root and sz==0){
        cccc_cnt++;
        cccc[cccc_cnt]={u};
        top--;
        return;
    }
    cnt=0;
    for(i=0;i<sz;i++){
        v=ss[u][i];
        if(!dfn[v]){
            cnt++;
            tarjan(v,root);
            low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u]){
                if(u!=root or cnt>=2) cut[u]=true;
                cccc_cnt++;
                cccc[cccc_cnt].clear();
                while(st[top]!=v){
                    cccc[cccc_cnt].push_back(st[top]);
                    top--;
                }
                cccc[cccc_cnt].push_back(st[top]);
                top--;
                cccc[cccc_cnt].push_back(u);
            }
        }else low[u]=min(low[u],dfn[v]);
    }
}
void clear_graph(){
    ll i;
    for(i=1;i<=mx;i++){
        ss[i].clear();
        dfn[i]=0;
        low[i]=0;
        cut[i]=false;
    }
    for(i=1;i<=cccc_cnt;i++) cccc[i].clear();
    top=0;
    timer=0;
    cccc_cnt=0;
    mx=0;
}
int main(){
    ll n,i,j,k,u,v,sz,ccnt,ans1,tc;
    ull ans2;
    scanf("%lld",&n);
    for(tc=1;n!=0;tc++){
        clear_graph();
        for(i=1;i<=n;i++){
            scanf("%lld%lld",&u,&v);
            ss[u].push_back(v);
            ss[v].push_back(u);
            mx=max(mx,max(u,v));
        }
        for(i=1;i<=mx;i++){
            if(!dfn[i]){
                top=0;
                tarjan(i,i);
            }
        }
        ans1=0;
        ans2=1;
        for(i=1;i<=cccc_cnt;i++){
            ccnt=0;
            sz=cccc[i].size();
            for(j=0;j<sz;j++){
                if(cut[cccc[i][j]]) ccnt++;
            }
            if(ccnt>=2) continue;
            if(ccnt==1){
                ans1++;
                ans2*=max(sz-1,1ll);
            }else{
                ans1+=2;
                ans2*=1ull*sz*(sz-1)/2;
            }
        }
        printf("Case %lld: %lld %llu\n",tc,ans1,ans2);
        scanf("%lld",&n);
    }
    return 0;
}