[HNOI2012]矿场搭建 BZOJ2730 点双+结论

Description

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

Input

输入文件有若干组数据，每组数据的第一行是一个正整数 N（N≤500），表示工地的隧道数，接下来的 N 行每行是用空格隔开的两个整数 S 和 T，表示挖 S 与挖煤点 T 由隧道直接连接。输入数据以 0 结尾。

Output

输入文件中有多少组数据，输出文件 output.txt 中就有多少行。每行对应一组输入数据的结果。其中第 i 行以 Case i: 开始（注意大小写，Case 与 i 之间有空格，i 与:之间无空格，: 之后有空格），其后是用空格隔开的两个正整数，第一个正整数表示对于第 i 组输入数据至少需要设置几个救援出口，第二个正整数表示对于第 i 组输入数据不同最少救援出口的设置方案总数。输入数据保证答案小于2^64。输出格式参照以下输入输出样例。

Sample Input

9
1 3
4 1
3 5
1 2
2 6
1 5
6 3
1 6
3 2
6
1 2
1 3
2 4
2 5
3 6
3 7
0

Sample Output

Case 1: 2 4
Case 2: 4 1

HINT

Case 1 的四组解分别是(2,4),(3,4),(4,5),(4,6)；

Case 2 的一组解为(4,5,6,7)。

分析：

先求出点双，之后发现只需要在每一个缩点之后的叶子节点建立一个即可，之后方案数就是大概那个意思，随便选一个不是割点的点即可。

附上代码：

#include <cstdio>

#include <cmath>

#include <iostream>

#include <queue>

#include <algorithm>

#include <cstring>

#include <cstdlib>

using namespace std;

#define N 1005

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

int head[N],cnt,dfn[N],low[N],tims,sta[N<<1],fa[N],iscut[N],m,top;vector<int>v[N];

void add(int x,int y){e[cnt]=(node){y,head[x],x};head[x]=cnt++;}

void tarjan(int x,int from)

{

    dfn[x]=low[x]=++tims;int num=0;

    for(int i=head[x];i!=-1;i=e[i].next)

    {

        int to1=e[i].to;if(to1==from)continue;

        if(!dfn[to1])

        {

            sta[++top]=i;tarjan(to1,x);low[x]=min(low[x],low[to1]);num++;

            if(low[to1]>=dfn[x])

            {

                iscut[x]=1;v[++cnt].clear();int u,y;

                while(1)

                {

                    u=e[sta[top]].from,y=e[sta[top]].to;top--;

                    if(fa[u]!=cnt)v[cnt].push_back(u),fa[u]=cnt;

                    if(fa[y]!=cnt)v[cnt].push_back(y),fa[y]=cnt;

                    if(u==x&&y==to1)break;

                }

            }

        }else if(dfn[to1]<dfn[x])low[x]=min(low[x],dfn[to1]),sta[++top]=i;

    }if(from==-1&&num==1)iscut[x]=0;

}

void init(){memset(fa,0,sizeof(fa));memset(head,-1,sizeof(head));memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));memset(iscut,0,sizeof(iscut));tims=cnt=0;}

int main()

{

    for(int cas=1;;cas++)

    {

        scanf("%d",&m);if(!m)break;init();int n=0;

        for(int x,y;m;m--)scanf("%d%d",&x,&y),add(x,y),add(y,x),n=max(n,max(x,y));cnt=0;

        for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i,-1);int ans1=0;long long ans2=1;

        for(int i=1;i<=cnt;i++)

        {

            int c=0;

            for(int j=0;j<v[i].size();j++)if(iscut[v[i][j]])c++;

            if(c==1)ans1++,ans2*=v[i].size()-1;

        }

        if(cnt==1)ans1=2,ans2=(v[1].size()-1)*v[1].size()/2;

        printf("Case %d: %d %lld\n",cas,ans1,ans2);

    }return 0;

}

巴特西