You have matrix a of size n × n. Let's number the rows of the matrix from 1 to n from top to bottom, let's number the columns from 1 to nfrom left to right. Let's use aij to represent the element on the intersection of the i-th row and the j-th column.
Matrix a meets the following two conditions:
- for any numbers i, j (1 ≤ i, j ≤ n) the following inequality holds: aij ≥ 0;
.
Matrix b is strictly positive, if for any numbers i, j (1 ≤ i, j ≤ n) the inequality bij > 0 holds. You task is to determine if there is such integer k ≥ 1, that matrix ak is strictly positive.
The first line contains integer n (2 ≤ n ≤ 2000) — the number of rows and columns in matrix a.
The next n lines contain the description of the rows of matrix a. The i-th line contains n non-negative integers ai1, ai2, ..., ain(0 ≤ aij ≤ 50). It is guaranteed that .
If there is a positive integer k ≥ 1, such that matrix ak is strictly positive, print "YES" (without the quotes). Otherwise, print "NO" (without the quotes).
2
1 0
0 1
NO
5
4 5 6 1 2
1 2 3 4 5
6 4 1 2 4
1 1 1 1 1
4 4 4 4 4
YES
题意：给你一个矩阵然后问你他的任意K次幂之后他是否全部大于0，一开始看上去很难，其实就是一个n个点的图是否全联通，就是从每一个点出发能到达所以其他点（学过离散数学应该一下就想到了）。
题解：用bitset<N>F[N]对矩阵进行预处理，1表示能到，0表示不能到。两重循环找到每一个点能到的点，这里采用位运算|=按位或，能省掉一重循环。这样之后如果图是全联通的，f[N][N]应该全为）；
下面代码
#include<iostream> #include<cstdio> #include<bitset> const int N=2005; using namespace std; bitset<N>f[N]; int n; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { int t; scanf("%d",&t); f[i][j]=t>0; //大于0就用1表示联通小与0则为0 } } for(int j=1;j<=n;j++) { for(int i=1;i<=n;i++) { if(f[i][j])f[i]|=f[j]; //如果i到j联通，则i与j按位或j能到的点i也能到 } } for(int i=1;i<=n;i++) { if(f[i].count()!=n) { puts("NO");return 0; } } puts("YES"); return 0; }
有个我也不太理解的地方，为什么那个进行位运算的两重循环不能反过来，路过的大佬们求教一下