[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;
}