poj 3660 Cow Contest (bitset+floyd传递闭包)

传送门

解题思路

考试题,想到传递闭包了,写了个O(n^3)的,T了7个点。。。后来看题解是tm的bitset优化???以前好像没听过诶(我太菜了),其实也不难,时间复杂度O(n^3/32)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<bitset> using namespace std;
const int MAXN = ; inline int rd(){
int x=,f=;char ch=getchar();
while(!isdigit(ch)) {f=ch=='-'?:;ch=getchar();}
while(isdigit(ch)) {x=(x<<)+(x<<)+ch-'';ch=getchar();}
return f?x:-x;
} int n,m,ans;
bitset<MAXN> a[MAXN]; int main(){
// freopen("rank.in","r",stdin);
// freopen("rank.out","w",stdout);
n=rd(),m=rd();int x,y;
while(m--){
x=rd(),y=rd();
a[x][y]=;
}
for(int k=;k<=n;k++)
for(register int i=;i<=n;i++)
if(a[i][k]) a[i]|=a[k];
for(int i=;i<=n;i++){
bool flag=;
for(register int j=;j<=n;j++) if(i!=j)
if(!a[i][j] && !a[j][i]) {flag=;break;}
if(flag) ans++;
}
printf("%d",ans);
return ;
}
上一篇:[Javascript] The Array forEach method


下一篇:win7 APPCRASH问题解决!