Codeforces Round #236 (Div. 2) E - Strictly Positive Matrix

根据线性代数的知识可知邻接矩阵自乘相当于做floyed

把输入转化为01矩阵(显然>1的数和1是等价的)得到邻接矩阵

问是否存在k次后所有数都为正数等价为自乘k次后所有点两两可达

转化为图论，用tarjan缩点判断scc的数目是否只有一个，或者直接bitset优化folyed也可以

#include<bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
const int N=2005;
int main(){
    fastio;
    bitset<N>f[N];
    int n;
    cin>>n;
    for(int _=1;_<=n;_++)
     for(int __=1;__<=n;__++){
         int x;cin>>x;
         f[_][__]=(x>0);
     }
    for(int i=1;i<=n;i++)
     for(int j=1;j<=n;j++)
      if(f[j][i]) f[j]|=f[i];
    
    for(int i=1;i<=n;i++){
        if(f[i].count()!=n) return puts("NO"),0; 
    }
    puts("YES");
}