Gym-100342J Triatrip(求有向图三元环个数+bitset应用)_有向图环路个数怎么计算

Description

Input

The first line of the input file contains two integer numbers n — the number of cities that are served by airlines that agree to sell their tickets via the agency (3 ≤ n ≤ 1500). The following n lines contain a sequence of n characters each — the j-th character of the i-th line is ‘+’ if it is possible to fly from the i-th city to the j-th one, and ‘-’ if it is not. The i-th character of the i-th line is ‘-’.

Output

Output one integer number — the number of triatrips that the agency can offer to its customers.

Sample Input

4
--+-
+--+
-+--
--+-

Sample Output

2

大致题意：

给出一个邻接矩阵表示的有向图，求三元环个数。

思路：

枚举每个点A，然后再枚举当前点能够到达的点B，将所有能够到达点A的点组成一个集合，B点能够到达的所有的点组成另一个集合，然后两个集合取交集，集合大小就是必走A->B边的三元环个数，最后ans/3去除重复统计的便是答案。在存储两个集合时用到bitset，求交集时可以进行一个常数优化。时间复杂度大致为O(n^3)，但网上有人说bitset之间位运算优化了大致为机器位数(32)的常数，所以这个复杂度能够解决当前问题。

代码：

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1505;
bitset<maxn> bt[maxn][2];
vector<int> vt[maxn];
char s[maxn];
int main()
{
	freopen("triatrip.in", "r", stdin);
	freopen("triatrip.out", "w", stdout);
	int n;
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i)
	bt[i][0].reset(), bt[i][1].reset(), vt[i].clear();
	for(int i = 1; i <= n; ++i)
	{
		scanf("%s", s+1);
		for(int j = 1; j <= n; ++j)
		if(s[j] == '+')
		{
			bt[i][1].set(j), bt[j][0].set(i);
			vt[i].push_back(j);
		}
	}
	LL ans = 0;
	for(int i = 1; i <= n; ++i)
	for(int j = 0; j < vt[i].size(); ++j)
	ans += 1ll*(bt[i][0] & bt[vt[i][j]][1]).count();
	printf("%lld\n", ans/3);
	return 0;
}

补充：

bitset(详)

#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int _inf = 0x7fffffff;
int main()
{
	cout << inf << endl;
	cout << _inf << endl;
	cout << "--------------------------------" << endl;
	string str = "1111111000000011001101";
	//从string对象读入位集的顺序是从右向左
	//从string中下标从5开始的6个字符初始化，整个字符串初始化 
	bitset<32> bt1(str, 5, 6), _bt1(str);
	//跟二进制类似，从右向左即从低位向高位 
	cout << bt1 << endl;
	cout << _bt1 << endl;
	//从低位开始输出 
	for(int i = 0; i <= 31; ++i)
	cout << bt1[i];
	cout << endl;
	bitset<16> bt2(16);
	bitset<32> bt3(0xffff);
	cout << bt2 << endl;
	cout << bt3 << endl;
	cout << "--------------------------------" << endl;
	bitset<32> bt4((string)"1101");
	bitset<32> bt5((string)"1111");
	cout << bt4 << endl;
	cout << bt4.count() << endl; 
	//可以像二进制一样进行位运算。优化了常数(32) 
	cout << (~bt4) << endl;
	cout << (bt4 & bt5) << endl;
	cout << (bt4 | bt5) << endl;
	cout << (bt4 ^ bt5) << endl;
	cout << (bt4 << 1) << endl;
	cout << (bt4 >> 1) << endl;
	return 0;
}

其它操作：

继续加油~