记录编号 |
436058 |
评测结果 |
AAAAAAAAAA |
题目名称 |
[HNOI 2012] 矿场搭建 |
最终得分 |
100 |
用户昵称 |
Hzoi_Ivan |
是否通过 |
通过 |
代码语言 |
C++ |
运行时间 |
0.003 s |
提交时间 |
2017-08-10 21:44:38 |
内存使用 |
0.36 MiB |
显示代码纯文本
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#define N 1500
using namespace std;
int n,m,cnt,num,tot,ans1,cosmos,bo[N];
long long ans2;
int dfn[N],low[N],judge[N],top,son,root;
int e=1,head[N];
struct edge{
int u,v,next;
}ed[5000];
void add(int u,int v){
ed[e].u=u; ed[e].v=v;
ed[e].next=head[u]; head[u]=e++;
}
void tarjan(int x,int f){
dfn[x]=low[x]=++top;
for(int i=head[x];i;i=ed[i].next){
int v=ed[i].v;
if(v==x) continue;
if(!dfn[v]){
tarjan(v,x);
low[x]=min(low[x],low[v]);
}
else{low[x]=min(low[x],dfn[v]);continue;}
if(dfn[x]<=low[v]){
if(x==root)son++;
else judge[x]=1;
}
}
}
void dfs(int x){
bo[x]=tot;
if(judge[x]) return;cnt++;
for(int i=head[x];i;i=ed[i].next){
int v=ed[i].v;
if(judge[v]&&bo[v]!=tot){num++;bo[v]=tot;}
if(!bo[v])dfs(v);
}
}
void init(){
memset(dfn,0,sizeof dfn);
memset(low,0,sizeof low);
memset(judge,0,sizeof judge);
memset(bo,0,sizeof bo); cosmos++;
n=0; ans1=0; ans2=1; tot=0; top=0;
e=1; memset(head,0,sizeof head);
}
int main(){
freopen("bzoj_2730.in","r",stdin);
freopen("bzoj_2730.out","w",stdout);
while(scanf("%d",&m)==1&&m!=0){
init();
int u,v;
for(int i=1;i<=m;i++){
scanf("%d%d",&u,&v);
n=max(n,max(u,v));
add(u,v); add(v,u);
}
for(int i=1;i<=n;i++){
if(!dfn[i]){
son=0; root=i;
tarjan(i,0);
if(son>1) judge[i]=1;
}
}
/*for(int i=1;i<=n;i++)
printf("%d %d\n",i,judge[i]);*/
for(int i=1;i<=n;i++){
if(!bo[i]&&!judge[i]){
tot++;cnt=num=0;
dfs(i);
if(!num){ans1+=2;ans2*=cnt*(cnt-1)/2;}
if(num==1){ans1++;ans2*=cnt;}
//printf("%d %d %d %d\n",i,tot,cnt,num);
}
}
printf("Case %d: %d %lld\n",cosmos,ans1,ans2);
}
return 0;
}
/*
5
1 2
2 3
1 3
3 4
1 4
*/