HNOI2012 矿场搭建

题目传送

sol:

首先需要对v-DCC缩点，对于缩点后的每一个连通块需分类讨论一下。

对于每一个连通块（v-DCC）：

1、不存在割点。需要建两个出口（毁掉一个还得有一个）。

2、存在一个割点。需要一个出口。（毁掉割点，走连通块内出口；毁掉连通块内出口，走割点到别的连通块出口）。

3、存在至少两个割点。不需要出口。（不管毁掉哪里，都能到别的连通块出口）。

方案的话就是把各个连通块的方案乘起来就好了。

#include<bits/stdc++.h>
#define IL inline
#define RG register
#define DB double
#define LL long long
using namespace std;

const int N=505;

LL ans2;
int n,m,RT,cnt,tot,top,ans1,Time,c[N],sta[N],low[N],dfn[N],cut[N],sum[N],head[N],eDcc[N][N];

struct EDGE{int next,to;}e[N<<1];

IL int gi() {
    RG int x=0,p=1; RG char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') p=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    return x*p;
}

IL void New_case() {
    n=tot=cnt=top=Time=0;
    memset(c,0,sizeof(c));
    memset(&e,0,sizeof(e));
    memset(head,0,sizeof(head));
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    memset(cut,0,sizeof(cut));
    memset(sum,0,sizeof(sum));
}
 
IL void make(int a,int b) {
    e[++tot]=(EDGE){head[a],b},head[a]=tot;
    e[++tot]=(EDGE){head[b],a},head[b]=tot;
}

void Tarjan(int x) {
    RG int i,k,y,num=0;
    dfn[x]=low[x]=++Time,sta[++top]=x;
    for(i=head[x];i;i=e[i].next)
        if(!dfn[y=e[i].to]) {
            Tarjan(y),++num,low[x]=min(low[x],low[y]);
            if(low[y]>=dfn[x]) {
                if(x!=RT||num>1) cut[x]=1;
                ++cnt;
                do{
                    k=sta[top--];
                    eDcc[cnt][++c[cnt]]=k;
                }while(k!=y);
                eDcc[cnt][++c[cnt]]=x;
            }
        }
        else low[x]=min(low[x],dfn[y]);
}

int main()
{
    RG int i,j,x,y,Case=0;
    while(scanf("%d",&m)!=EOF&&m) {
        New_case();
        for(i=1;i<=m;++i)
            x=gi(),y=gi(),n=max(n,max(x,y)),make(x,y);
        for(i=1;i<=n;++i)
            if(!dfn[i]) RT=i,Tarjan(i);
        for(i=1;i<=cnt;++i)
            for(j=1;j<=c[i];++j) sum[i]+=cut[eDcc[i][j]];
        for(i=1,ans1=0,ans2=1;i<=cnt;++i)
            if(!sum[i]) ans1+=2,ans2*=c[i]*(c[i]-1)/2;
            else if(sum[i]==1) ++ans1,ans2*=c[i]-1;
        printf("Case %d: %d %lld\n",++Case,ans1,ans2);
    }
    return 0;
}