【bitset】【推导】hdu5961 传递

<法一>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 传递

最新文章

热门文章