[HNOI2012]矿场搭建题解

[HNOI2012]矿场搭建

时间限制: 1 Sec 内存限制: 128 MB

题目描述

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

输入

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

输出

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

样例输入

样例输出

Case 1: 2 4

Case 2: 4 1

提示

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

　　不知道有没有萌新和我一样，以为输出一个出去割点的联通块的个数和各个联通块的大小就完事了，事实证明，如果你A了超过1/3的点，算我输。

　　事实上我们应当去对各个联通块进行分析，第一种，联通块在求的时候就没有碰到割点，那么它其实应该放两个安全出口，因为如果你放的那个刚好出了事故就没有别的安全出口了。第二种，只碰到了一个割点，那么就放一个出口就OK了。第三种，碰到了两个及两个以上的割点，那么我们就不用放了，无论那个割点出了事故我们都可以从别的地方走。

　　至于方案数么，一个割点都没有的是size*(size-1)/2，注意特判size=1，有一个割点是size，有两个及两个以上割点无贡献。应该不用再分析了吧……

 #include<iostream>

 #include<cstdlib>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<map>

 #include<queue>

 #include<string>

 #include<cmath>

 using namespace std;

 struct ro{

     int to,next;

 }road[];

 int zz,a[];

 void build(int x,int y){

     zz++;

     road[zz].to=y;

     road[zz].next=a[x];

     a[x]=zz;

 }

 int v[],zz2,dfn[],low[];

 void tar(int x,int root){

     zz2++;

     v[x]=;

     dfn[x]=low[x]=zz2;

     for(int i=a[x];i>;i=road[i].next)

     {

         int y=road[i].to;

         if(!v[y])

         {

             tar(y,root);

             low[x]=min(low[x],low[y]);

             if(dfn[x]<=low[y])

             {

                 v[x]++；

             }

         }

         else

         {

             low[x]=min(low[x],dfn[y]);

         }

     }

     if((x==root&&v[x]>)||(x!=root&&v[x]>))

         {

             v[x]=;

         }

         else

             v[x]=;

 }

 int m,top,st[],bj,jj,size,zzzz;

 bool rz[],rz2[];

 void work(int x){

     zz2++;

     dfn[x]=low[x]=zz2;

     rz[x]=rz2[x]=;

     top++;

     st[top]=x;

     for(int i=a[x];i>;i=road[i].next)

     {

         int y=road[i].to;

         if(v[y]==)

         {

             if(!bj)

             {

                 bj=y;

                 jj=;

             }

             else if(bj!=y) jj=;

             continue;

         }

         if(!rz2[y])

         {

             work(y);

             low[x]=min(low[x],low[y]);

         }

         else if(rz[y])

         {

             low[x]=min(low[x],dfn[y]);

         }

     }

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

     {

         int v;

         zzzz++;

         do{

             v=st[top];

             top--;

             size++;

         }while(dfn[v]!=low[v]);

     }

 }

 int n;

 int main(){

 //  freopen("bzoj_2730.in","r",stdin);

 //  freopen("bzoj_2730.out","w",stdout);

     int js=;

 while(~scanf("%d",&m))

 {

     if(m==) break;

     js++;

     zz=;

     memset(a,,sizeof(a));

     n=;

     for(int i=;i<=m;i++)

     {

         int x,y;

         scanf("%d%d",&x,&y);

         build(x,y);

         build(y,x);

         n=max(n,max(x,y));

     }

     memset(v,,sizeof(v));

     memset(dfn,,sizeof(dfn));

     memset(low,,sizeof(low));

     zz2=;

     for(int i=;i<=n;i++)

     {

         if(!v[i])

         {

             zz2=;

             tar(i,i);

         }

     }

     memset(dfn,,sizeof(dfn));

     memset(low,,sizeof(low));

     zz2=;

     memset(rz,,sizeof(rz));

     memset(rz2,,sizeof(rz2));

     long long an=,ans=;

     top=;

     memset(st,,sizeof(st));

     for(int i=;i<=n;i++)

     {

         if(!rz2[i]&&v[i]!=)

         {

             jj=;

             bj=;

             size=;

             work(i);

             if(!jj)

             {

                 an+=;

                 if(size!=) ans*=(size*(size-))/;

             }

             else if(jj==)

             {

                 an++;

                 ans*=size;

             }

         }

     }

     printf("Case %d: %lld %lld\n",js,an,ans);

 }

     //while(1);

     return ;

 }

巴特西

[HNOI2012]矿场搭建题解