[ABC258G] Triangle 题解

题目链接：[ABC258G] Triangle

题意：

给你一个简单的无向图，其中有 \(N\) 个顶点。用一个 的 \(N\times N\) 邻接矩阵 \(A\) 来表示。如果 \(A_{i,j}=1\) ,则表示 \(i\) 到 \(j\) 有边相连，如果 \(A_{i,j}=0\) ,则表示 \(i\) 到 \(j\) 无边相连。

求三角形 \((i,j,k)\) 的个数，满足 \(1\leq i < j < k\leq n\)，且 \(i\) 与 \(j\) 有边相连，\(i\) 与 \(k\) 有边相连，\(j\) 与 \(k\) 有边相连。

数据范围：

\(3 \le n \le 3000\)

一直没写题啊。

注意到这个三角形具有 \(i,j\) 均能到 \(k\) 的性质。不妨预处理出所有点能到达的点，然后枚举 \(i,j\) 。

时间复杂度 \(\mathcal{O}(n^2)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(3e3 + 15))

int n,res; char s[N]; bitset<N> a[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> (s + 1);
        for(int j = i + 1; j <= n; j++) a[i][j] = s[j] - '0';
    }
    for(int i = 1; i <= n; i++) 
        for(int j = i + 1; j <= n; j++) {
            if(a[i][j]) res += (a[i] & a[j]).count();
        }
    cout << res << '\n';
    return 0;
}