1348. [HNOI2012]矿场搭建

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

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

  1 #include<iostream>  2 #include<cstdio>  3 #include<cstring>  4 #include<algorithm>  5 using namespace std;  6 #define N 505  7 int read() {  8     int s=0,f=1;  9     char ch=getchar(); 10     while(ch>‘9‘||ch<‘0‘) { 11         if(ch==‘-‘) { 12             f=-1; 13         } 14         ch=getchar(); 15     } 16     while(ch>=‘0‘&&ch<=‘9‘) { 17         s=(s<<1)+(s<<3)+(ch^48); 18         ch=getchar(); 19     } 20     return s*f; 21 } 22 long long ji,nn; 23 int kk,T,cnt,mx,belong[505],num[505],n,tot,r[505],dfn[505],low[505],tim,fa[505]; 24 bool conn[505][505],is_cut[505]; 25 struct edge { 26     int to,next; 27 } c[250005]; 28 void add(int x,int y) { 29     c[tot]=(edge) { 30         y,r[x] 31     }; 32     r[x]=tot++; 33 } 34 void clean() { 35     kk=T=nn=ji=mx=cnt=tot=tim=0; 36     memset(r,-1,sizeof(r)); 37     memset(c,0,sizeof(c)); 38     memset(dfn,-1,sizeof(dfn)); 39     memset(low,0,sizeof(low)); 40     memset(fa,0,sizeof(fa)); 41     memset(is_cut,false,sizeof(is_cut)); 42     memset(num,0,sizeof(num)); 43     memset(belong,0,sizeof(belong)); 44 } 45 class oo { 46     public: 47         void work() { 48             tarjan(1,-1); 49             int root=0; 50             for(int i=2; i<=mx; ++i) { 51                 int v=fa[i]; 52                 if(v==1) { 53                     ++root; 54                 } else { 55                     if(low[i]>=dfn[v]&&v) { 56                         is_cut[v]=true; 57                         ++kk; 58                     } 59                 } 60             } 61             if(root>1) { 62                 is_cut[1]=true; 63                 ++kk; 64             } 65         } 66     private: 67         void tarjan(int x,int f) { 68             fa[x]=f; 69             dfn[x]=low[x]=tim++; 70             for(int i=r[x]; ~i; i=c[i].next) { 71                 if(dfn[c[i].to]==-1) { 72                     tarjan(c[i].to,x); 73                     low[x]=min(low[x],low[c[i].to]); 74                 } else { 75                     if(c[i].to!=f) { 76                         low[x]=min(low[x],dfn[c[i].to]); 77                     } 78                 } 79             } 80         } 81 } cut_point; 82 int hh; 83 void dfs(int x) { 84     belong[x]=T; 85     if(is_cut[x]) return; 86     nn++; 87     for(int i=r[x]; ~i; i=c[i].next) { 88         if (is_cut[c[i].to]&&belong[c[i].to]!=T) { 89             ji++,belong[c[i].to]=T; 90         } 91         if (!belong[c[i].to]) { 92             dfs(c[i].to); 93         } 94     } 95 } 96 int Main(){ 97     freopen("bzoj_2730.in","r",stdin); 98     freopen("bzoj_2730.out","w",stdout); 99     while(~scanf("%d",&n)&&n) {100         clean();101         for(int x,y,i=1; i<=n; ++i) {102             x=read(),y=read();103             add(x,y),add(y,x);104             mx=max(mx,max(x,y));105         }106         cut_point.work();107         if(!kk) {108             int ans1=2;109             long long ans2=mx*(mx-1)/2;110             hh++;111             printf("Case %d: %d %lld\n",hh,ans1,ans2);112             continue;113         }114         int ans1=0;115         long long ans2=1;116         for (int i=1; i<=mx; i++){117             if(!belong[i]&&!is_cut[i]) {118                 ++T;119                 ji=nn=0;120                 dfs(i);121                 if(!ji) {122                     ans1+=2;123                     ans2*=nn*(nn-1)/2;124                 }125                 if(ji==1) {126                     ans1++;127                     ans2*=nn;128                 }129             }130         }131         hh++;132         printf("Case %d: %d %lld\n",hh,ans1,ans2);133     }134     return 0;135 }136 int hehe=Main();137 int main(){138     ;139 }