ABC 258 G Triangle(bitset 优化)

ABC 258 G Triangle(bitset 优化)

ABC 258 G Triangle

大意：给出一个邻接矩阵 ，用来记录两两元素间是否连接 ， 计算其中三元环的数目。

思路：

不妨先想暴力解法

for(int i = 1 ; i <= n ; i ++){for(int j = i + 1 ; j <= n ; j ++){for(int k = j + 1 ; k <= n ; k ++){res += (a[i][j] && a[j][k] && a[k][i]);}}}

考虑 bitset 优化这个式子 ， 可以仿照传递闭包的优化方式

优化成 if(a[i][j]) res += (a[i] & a[j]).count();

注意这样会重复计数 ， 去重即可。

对于一个三元组 ， 我们要求 第二维大于第一维 ， 以 (1 ， 2 ， 3) 为例 ， 会有 (1 , 2 , 3) (1 , 3 , 2) (2 , 3 , 1) 三种计数方式 ， 也就是每个三元组重复记录了三次 ， 除 3 即可。

$$时间复杂度O(\frac{n^3}{w})$$

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N = 5e3 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;bitset<N>bit[N];
int n , a[N][N];
string s;
signed main(){IOScin >> n;for(int i = 1 ; i <= n ; i ++){cin >> s;for(int j = 0 ; j < n ; j ++){if(s[j] == '0') a[i][j + 1] = 0;else a[i][j + 1] = bit[i][j + 1] = 1;}}int cnt = 0;for(int i = 1 ; i <= n ; i ++){for(int j = i + 1 ; j <= n ; j ++){if(a[i][j]) cnt += (bit[i] & bit[j]).count(); }}cout << cnt / 3 << "\n";return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);