[HNOI2012]矿场搭建（tarjan求点双）

题目

Description

煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见，希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设立救援出口，使得无论哪一个挖煤点坍塌之后，其他挖煤点的工人都有一条道路通向救援出口。

请写一个程序，用来计算至少需要设置几个救援出口，以及不同最少救援出口的设置方案总数。

Input

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

Output

输入文件中有多少组数据，输出文件中就有多少行。每行对应一组输入数据的结果。

其中第 i 行以 Case i: 开始（注意大小写，Case 与 i 之间有空格，i 与 : 之间无空格，: 之后有空格），其后是用空格隔开的两个正整数，第一个正整数表示对于第 i组输入数据至少需要设置几个救援出口，第二个正整数表示对于第 i 组输入数据不同最少救援出口的设置方案总数。

输出格式参照以下输入输出样例。

题解

再点双连通分量中，如果坏了其中一个点，那么剩下的点还是连通的，所以我们求一次点双连通分量，再仔细观察一下，如果一个点双中（非割点点数为 \(n\)）：

没有割点，那么显然要两个通道，共 \(C_n^2\) 种选法。
有一个割点，那么在这个点双中就要有一个通道，共，有一个割点，那么在这个点双中就要有一个通道，共 \(n\) 种选法。
有两个或者两个以上的割点，则不需要通道。

问题解决了，不过我可能是太弱了，统计割点数和非割点数写挂了，我们其实可以把每个割点找出来，dfs 一遍，割点之间就是一个点双，另外相邻的割点也属于这个点双。

CODE

#include<iostream>

#include<stack>

#include<cstring>

#include<cstdio>

using namespace std;

int dfn[10005],low[10005],cp[10005],cnt=0;

int bcc[10005],num[10005],son[10005],C=0;

bool vis[100005],iscp[100005];

int n,m,x,y,h[100005],tot=0,cas=0;

struct Edge{

	int x,next;

}e[200005];

inline void add_edge(int x,int y){

	e[++tot].x=y;

	e[tot].next=h[x],h[x]=tot;

}

stack<int> s;

void tarjan(int x,int fa){

	low[x]=dfn[x]=++cnt;

	son[x]=0;

	for(int i=h[x];i;i=e[i].next){

		if(e[i].x==fa)continue;

		if(!dfn[e[i].x]){

			tarjan(e[i].x,x),son[x]++;

			low[x]=min(low[x],low[e[i].x]);

			if(low[e[i].x]>=dfn[x]&&fa!=0)iscp[x]=true;

		}

		else low[x]=min(low[x],dfn[e[i].x]);

	}

	if(son[x]>1&&fa==0)iscp[x]=true;

}

void dfs(int x){

	vis[x]=true,num[C]++;

	for(int i=h[x];i;i=e[i].next){

		if(vis[e[i].x])continue;

		if(!iscp[e[i].x])dfs(e[i].x);

		else{

			if(bcc[e[i].x]!=C)

				bcc[e[i].x]=C,cp[C]++;

		}

	}

}

int main(){

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

		memset(h,0,sizeof(h));

		memset(dfn,0,sizeof(dfn));

		memset(low,0,sizeof(low));

		memset(bcc,0,sizeof(bcc));

		memset(num,0,sizeof(num));

		memset(cp,0,sizeof(cp));

		memset(iscp,0,sizeof(iscp));

		memset(vis,0,sizeof(vis));

		tot=cnt=C=n=0;

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

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

			add_edge(x,y);

			add_edge(y,x);

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

		}

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

			if(!dfn[i])tarjan(i,0);

		unsigned long long sum=0,ans=1;

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

			if(!iscp[i]&&!vis[i]){

				C++,dfs(i);

				if(cp[C]==1)sum++,ans*=num[C];

			}

		}

		if(C==1)sum=2,ans=n*(n-1)/2;

		printf("Case %d: ",++cas);

		printf("%llu %llu\n",sum,ans);

	}

}

巴特西

[HNOI2012]矿场搭建（tarjan求点双）

题目

Description

Input

Output

题解

CODE

最新文章

热门文章