首页 > 代码库 > 【bitset】【推导】hdu5961 传递
【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 传递
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。