[HNOI2012]矿场搭建/Mining Your Own Business

洛咕

双倍经验

三倍经验

题意:煤矿工地可以看成是由\(n(n<=50000)\)条隧道连接挖煤点组成的无向图.为安全起见，希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处.于是矿主决定在某些挖煤点设立救援出口，使得无论哪一个挖煤点坍塌之后，其他挖煤点的工人都有一条道路通向救援出口.请写一个程序，用来计算至少需要设置几个救援出口，以及不同最少救援出口的设置方案总数。

分析:首先注意一下题目给出了n条边但并未说明只有n个点,注意每次加边时对点数取个max,记为m,表示总共有m个点.

首先跑tarjan求出哪些点是割点,记为\(cut[x]=1\).求出割点后,我们跑dfs求联通块.对于每一个联通块,我们求出块内割点的个数\(sum_{cut}\)和非割点的个数\(size\).

先说明一下设置救援点时的考虑,本着安全第一的原则,我们要按照最坏的情况来打算(尽管题目问的是"至少").

那么对于每个联通块统计答案时,如果块内没有割点,那么该块需要在任意两个非割点处设置两个救援点,为什么是两个?因为要考虑你设置的某个救援点正好出现坍塌(最坏情况),所以两个才是最稳妥的.同时方案数就是\(C_{size}^2=size*(size-1)/2.\)

如果块内有1个割点,如果正好是割点坍塌(最坏情况),那么我们就要设置一个救援点,方案数就是\(C_{size}^1=size\)

如果块内有两个及以上的割点,那么我们不用设置救援点,因为不论哪个割点坍塌,图仍然连通.

根据乘法原理,方案数应该要累乘起来.并且记得开long long.

多组数据的初始化很烦人.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
const int N=100005;
int n,m,Case;ll ans1,ans2;
int size,sum_cut,group,visit[N];
int root,timeclock,dfn[N],low[N],cut[N];
int tot,head[N],nxt[N],to[N];
inline void add(int a,int b){
    nxt[++tot]=head[a];head[a]=tot;to[tot]=b;
}
inline void tarjan(int u){
    dfn[u]=low[u]=++timeclock;
    int child=0;
    for(int i=head[u];i;i=nxt[i]){
        int v=to[i];
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u]){
                ++child;
                if(u!=root||child>=2)cut[u]=1;
            }
        }
        else low[u]=min(low[u],dfn[v]);
    }
}
inline void dfs(int u){
    visit[u]=group;++size;
    for(int i=head[u];i;i=nxt[i]){
        int v=to[i];
        if(cut[v]&&visit[v]!=group){
            ++sum_cut;
            visit[v]=group;
        }
        if(!visit[v])dfs(v);
    }
}
int main(){
    while(1){
        int n=read();if(!n)return 0;
        m=tot=timeclock=group=ans1=0;ans2=1;
        memset(head,0,sizeof(head));
        memset(dfn,0,sizeof(dfn));
        memset(low,0,sizeof(low));
        memset(cut,0,sizeof(cut));
        memset(visit,0,sizeof(visit));
        printf("Case %d: ",++Case);
        for(int i=1;i<=n;++i){
            int a=read(),b=read();
            add(a,b);add(b,a);
            m=max(m,max(a,b));
        }
        for(int i=1;i<=m;++i)
            if(!dfn[i])root=i,tarjan(i);
        for(int i=1;i<=m;++i)
            if(!visit[i]&&!cut[i]){
                size=sum_cut=0;++group;
                dfs(i);
                if(sum_cut==0){
                    ans1+=2;
                    ans2=1ll*ans2*size*(size-1)/2;
                }
                if(sum_cut==1){
                    ans1+=1;
                    ans2=1ll*ans2*size;
                }
            }
        printf("%lld %lld\n",ans1,ans2);
    }
    return 0;
}

[HNOI2012]矿场搭建/Mining Your Own Business

原文：https://www.cnblogs.com/PPXppx/p/11380973.html