算法1
(暴力枚举+卡常) $O(\frac{n^3}{6})$
可以关掉 io
同步,并采用 $\operatorname{Qcfium}$ 法
C++ 代码
#pragma GCC optimize ("O2")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target ("avx2")
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
using std::string;
using ll = long long;
int main() {
cin.tie(nullptr) -> sync_with_stdio(false);
int n;
cin >> n;
vector a(n, vector<int>(n));
rep(i, n) {
string s;
cin >> s;
rep(j, n) if (s[j] == '1') a[i][j] = 1;
}
ll ans = 0;
rep(i, n)rep(j, i) {
if (a[i][j]) {
rep(k, j) ans += a[i][k] & a[j][k];
}
}
cout << ans << '\n';
return 0;
}
算法2
(暴力枚举+卡常) $O(\frac{n^3}{64})$
也可以用 $\operatorname{bitset}$ 优化
C++ 代码
#pragma GCC optimize ("O2")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target ("avx2")
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
using std::bitset;
using std::string;
using ll = long long;
int main() {
cin.tie(nullptr) -> sync_with_stdio(false);
int n;
cin >> n;
vector<bitset<3000>> g(n);
rep(i, n) {
string s;
cin >> s;
rep(j, n) g[i][j] = s[j]-'0';
}
ll ans = 0;
rep(i, n)rep(j, i) if (g[i][j]) {
ans += (g[i]&g[j]).count();
}
ans /= 3;
cout << ans << '\n';
return 0;
}
算法3
(根号分治) $O(M\sqrt{M})$
考虑为每条边重新定义方向:
- 由两端点中度数小的点指向度数大的点;
- 若两端点度数一样,则由编号小的点指向编号大的点
这样就能保证图上每点的出度都不超过 $O(\sqrt{M})$,其中 $M = O(N^2)$
但这里 $M$ 比较大,所以会挂