Codeforces Gym 100342J Problem J. Triatrip (bitset)

http://codeforces.com/gym/100342

题意：给一个又向图，求其中三元环的个数，点数$n (3 ≤ n ≤ 1500)$。

显然可以想到暴力的$O(n^3)$，但是$n$最大到1500，所以考虑用bitset优化，开两个bitset数组$a[i]$和$b[i]$。对于从$i$指向$j$的边，我们令$a[i][j]=1,b[j][i]=1$，这样$a[i]$表示从$i$发出的终点的集合，$b[i]$表示到达$i$的边的起点的集合。然后枚举边，对于边$i→j$，只要将$a[j]$和$b[i]$并起来就是与这条边构成三元环的点集，统计这些点集中点的个数$ans$，因为每个三元环都要重复计算三遍，所以最后答案是$ans/3$。
要注意的是这个题要用文件输入输出。。。

#include<iostream>
#include<cstdio>
#include<stack>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<cmath>
#include<bitset>using namespace std;bitset<1510> a[1510],b[1510],p;
char mp[1510][1510];
int n;
long long ans;
int main()
{freopen("triatrip.in","r",stdin);freopen("triatrip.out","w",stdout);scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%s",mp[i]+1);}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(mp[i][j]=='+'){a[i][j]=b[j][i]=1;}}}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(a[i][j]){p=a[j]&b[i];ans+=p.count();}}}printf("%lld\n",ans/3);return 0;
}