西安网站建设huanxi,做家装的设计公司网站,想学网店运营去哪里学啊,广西网站设计服务题干#xff1a; 给你一个二维字符矩阵#xff0c;如果 ( i , j ) 为 表明 两点之间有一条有向边#xff0c;为-表示没有边#xff0c;那么你要找出所有的三元环的个数。顶点数N1500。
解题报告#xff1a; 考虑最暴力的方法#xff0c;开个二维数组来存每两个顶点之…题干 给你一个二维字符矩阵如果 ( i , j ) 为 表明 两点之间有一条有向边为-表示没有边那么你要找出所有的三元环的个数。顶点数N1500。
解题报告 考虑最暴力的方法开个二维数组来存每两个顶点之间的邻接关系但是N^3肯定是会TLE的考虑bitset压位优化。神奇
AC代码
#includebits/stdc.husing namespace std;const int N 1500 10;
bitsetN in[N], out[N];
int a[N][N], ans;int main()
{int n;long long ans 0;char c;scanf(%d, n);for(int i 1; i n; i)for(int j 1; j n; j) {cin c;if(c ) {a[i][j] 1;out[i][j] 1;in[j][i] 1;}}for(int i 1; i n; i)for(int j 1; j n; j)if(a[i][j])ans (out[j] in[i]).count();cout ans / 3 endl;return 0;
}/*
4
---
--
---
---
4
-
-
-
---
43*/
