首页 > 代码库 > 【bitset】【推导】hdu5961 传递

【bitset】【推导】hdu5961 传递

2024-09-28 03:06:39   218人阅读

<法一>http://blog.csdn.net/u014325920/article/details/53046890

1、判断传递的条件为：若G中有 一条边从a到b且有一条边从b到c ,则G中同样有一条边从a到c。 
2、我们去枚举b，我们假设集合Sb={x|x?>b}表示有一条x指向b的边。我们假设集合Tb={x|b?>x}，表示有有一条b指向x的边。 
3、我们再去枚举Sb中的元素，假设我们当前枚举的是x，因为x是指向b的，所以我们根据题意容易得知该图是传递图的话一定满足：Tx∩Tb=Tb，然后就可以得出答案了，至于怎么处理集合的并，我们可以用bitset搞搞就可以了！！！具体看代码。

<法二>http://www.cnblogs.com/zarth/p/6671252.html

技术分享

 

 

给出法一的代码

#include<cstdio>
#include<bitset>
using namespace std;
bitset<2030> S[2030];
int T,n;
char a[2030][2030];
int main(){
	scanf("%d",&T);
	for(;T;--T){
		for(int i=1;i<=n;++i){
			S[i].reset();
		}
		scanf("%d",&n);
		for(int i=1;i<=n;++i){
			scanf("%s",a[i]+1);
		}
		for(int i=1;i<=n;++i){
			for(int j=1;j<=n;++j){
				if(a[i][j]==‘P‘){
					S[i].set(j);
				}
			}
		}
		bool flag=1;
		for(int i=1;i<=n;++i){
			for(int j=1;j<=n;++j){
				if(a[i][j]==‘P‘){
					if((S[j]|S[i])!=S[i]){
						flag=0;
						goto OUT;
					}
				}
			}
		}
		OUT:
		if(!flag){
			puts("N");
			continue;
		}
		flag=1;
		for(int i=1;i<=n;++i){
			S[i].reset();
		}
		for(int i=1;i<=n;++i){
			for(int j=1;j<=n;++j){
				if(a[i][j]==‘Q‘){
					S[i].set(j);
				}
			}
		}
		for(int i=1;i<=n;++i){
			for(int j=1;j<=n;++j){
				if(a[i][j]==‘Q‘){
					if((S[j]|S[i])!=S[i]){
						flag=0;
						goto OUT2;
					}
				}
			}
		}
		OUT2:
		if(!flag){
			puts("N");
		}
		else{
			puts("T");
		}
	}
	return 0;
}

【bitset】【推导】hdu5961 传递


联系
我们