1 second
256 megabytes
standard input
standard output
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=;
using namespace std;
bitset<N>f[N];
int n;
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
{
for(int j=;j<=n;j++)
{
int t;
scanf("%d",&t);
f[i][j]=t>; //大于0就用1表示联通小与0则为0
}
}
for(int j=;j<=n;j++)
{
for(int i=;i<=n;i++)
{
if(f[i][j])f[i]|=f[j]; //如果i到j联通，则i与j按位或j能到的点i也能到
}
}
for(int i=;i<=n;i++)
{
if(f[i].count()!=n)
{
puts("NO");return ;
}
}
puts("YES");
return ;
}
有个我也不太理解的地方，为什么那个进行位运算的两重循环不能反过来，路过的大佬们求教一下