题意简述
给定一张无向图，若图中三个点 \(a\)，\(b\)，\(c\) 满足 \(a\) 与 \(b\) 有边相连，\(a\) 与 \(c\) 有边相连，\(b\) 与 \(c\) 有边相连，则称点 \(a\)，\(b\)，\(c\) 构成了一个三角形，求在给定的图中三角形的个数。
题目分析
一个比较直接的想法是枚举 \(a\)，\(b\)，\(c\) 的编号，时间复杂度为 \(O(n^3)\)，无法通过本题。
我们可以只枚举 \(a\)，\(b\) 的编号，若一个点与 \(a\) 有边相连且与 \(b\) 有边相连，则这个点必定是满足条件的点 \(c\)。使用 bitset 可以比较方便地解决这个问题。
Code
#include<bits/stdc++.h>
using namespace std;
long long n,ans;
bitset<3005> m[3005];
char t;
int main(){
cin>>n;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>t;
if(t=='1') m[i][j]=1;
else m[i][j]=0;
}
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(m[i][j]){
ans+=(long long)((m[i]&m[j]).count());//满足条件的c点个数
}
}
}
cout<<ans/6<<endl;//统计出的结果有一定的重复，需要除以6后再输出
return 0;
}