CodeForces 100342 (Triatrip)[bitset]

题目链接:http://codeforces.com/gym/100342/attachments

题目大意:给定一张有向图,询问有多少个三元环。

这道题数据范围只有1500,所以可以n^2,我们暴力枚举两个点,假设为A->B,然后我们预处理出有哪些点可以到A,B可以到哪些点,这样就可以得到俩集合,然后再交一下,再统计一下集合里面元素的个数就好了
引用自qscqesze

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <bitset>
using namespace std;
const int maxn=1509;
typedef long long ll;
bitset<maxn> g[maxn];
char s[maxn];
int main() {
freopen("triatrip.in","r",stdin);
freopen("triatrip.out","w",stdout);
int n;
scanf("%d",&n);
for(int i=0;i<n;i++) {
scanf("%s",s);
for(int j=0;s[j]!='\0';j++)
if(s[j]=='+') g[i].set(j);
}
ll ans=0;
bitset<maxn> tmp(0);
for(int i=0;i<n;i++) {
tmp.reset();
for(int j=0;j<n;j++) {
if(i==j) continue;
if(g[j].test(i)) tmp.set(j);
}
for(int j=0;j<n;j++) {
if(i==j) continue;
if(g[i].test(j)) ans+=(tmp&g[j]).count();
}
}
printf("%lld",ans/3);
}