题意:
给定图的邻接矩阵,问三元环的数量
\(n\le 3000\)
思路:
\(O(n^3)\) 的最naive的暴力,用 bitset
优化到 \(O(n^3/64)\)
暴力搜 \((i,j)\),则另外两个点 \((i,k),(j,k)\) 在同一列
Since \(\frac{3000^3}{64}=421875000\) \(\simeq\) \(4\) \(\times\) \(10^8\), this solution is fast enough. We may further halve the execution time by only searching \((i,j)\) such that \(i< j\).
// 850ms
void sol() {
int n; cin >> n;
vector<bitset<3000> > a(n);
for(int i = 0; i < n; i++) {
string s; cin >> s;
for(int j = 0; j < n; j++)
a[i][j] = s[j] == '1';
}
long long ans = 0;
for(int i = 0; i < n; i++)
for(int j = 0; j < i; j++)
if(a[i][j]) ans += (a[i] & a[j]).count();
cout << ans / 3;
}
标签:Triangle,int,cin,++,64,3000,abc258
From: https://www.cnblogs.com/wushansinger/p/17045193.html