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);
}