[HNOI2012]矿场搭建

2730: [HNOI2012]矿场搭建

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 3565 Solved: 1700
[Submit][Status][Discuss]

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)。

Source

day1

[Submit][Status][Discuss]
HOME Back

题解

如果被禁的点是割点，那么无影响。

先求出整个图的割点,通过删去割点得到的连通图就是bcc了,对于单个bcc,如果有超过2个割点连接,那么能不设置出口,通过无论哪个割点被删除都能从另一个割点出去,如果只有一个割点,那么bcc中除了割点的点都能作为出口.然后乘法求方案数.

注意标记的更改。

#include<bits/stdc++.h>
#define rg register
#define il inline
#define co const
template<class T>il T read(){
    rg T data=0,w=1;rg char ch=getchar();
    for(;!isdigit(ch);ch=getchar())if(ch=='-') w=-w;
    for(;isdigit(ch);ch=getchar()) data=data*10+ch-'0';
    return data*w;
}
template<class T>il T read(rg T&x) {return x=read<T>();}
typedef unsigned long long ull;
using namespace std;

co int N=1e3+1;
int n,m,num,anscnt,data;
int v[N],w[N],dfn[N],low[N];
vector<int> e[N];
ull ans;

void tarjan(int x){
	dfn[x]=low[x]=++num;
	v[x]=1;
	for(unsigned i=0;i<e[x].size();++i){
		int y=e[x][i];
		if(!v[y]){
			tarjan(y);
			low[x]=min(low[x],low[y]);
			if(dfn[x]<=low[y]) ++v[x];
		}
		else low[x]=min(low[x],dfn[y]);
	}
	if(x==1&&v[x]>2||x>1&&v[x]>1) v[x]=2; // cut vertice
    else v[x]=1; // edit 1: must be set 1
}
void dfs(int x,int&flag,int&cnt){
	v[x]=3;
	++cnt;
	for(unsigned i=0;i<e[x].size();++i){
		int y=e[x][i];
		if(v[y]==1) dfs(y,flag,cnt);
		else if(v[y]==2&&w[y]!=num){
			++flag;
			w[y]=num;
		}
	}
}
void work(){
	for(int i=0;i<N;++i) e[i].clear();
	n=0,memset(v,-1,sizeof v);
	for(int x,y;m--;){
		read(x),read(y);
		n=max(n,max(x,y));
		v[x]=v[y]=0;
		e[x].push_back(y),e[y].push_back(x);
	}
	num=0;
	for(int i=1;i<=n;++i)
		if(!v[i]) tarjan(i);
	num=0,memset(w,0,sizeof w),anscnt=0,ans=1;
	for(int i=1;i<=n;++i)if(v[i]==1){
		++num;
		int flag=0,cnt=0;
		dfs(i,flag,cnt);
		if(flag==1) ++anscnt,ans*=cnt;
	}
	if(!anscnt) anscnt=2,ans=n*(n-1)/2;
	printf("Case %d: %d %lld
",++data,anscnt,ans);
}
int main(){
	while(read(m)) work();
	return 0;
}