E. Strictly Positive Matrix [强联通+矩阵幂转图论+缩点] 好题

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.

Input

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 .

Output

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).

        Examples       
          input                     Copy          
2
1 0
0 1
          output         
NO
          input                     Copy          
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
          output         
YES

题意:给定一个矩阵A,其中A[i][j]>=0 && sigma[i][i]>0 问,是否存在K,使得B=A^K,其中B[i][j]>0

思路:矩阵乘法转图论. A^k大于0,代表所有元素直接是联通.

B=A^K 中 b[i][j]代表i到j长度为k的路条数

#include<bits/stdc++.h>
#define bug cout <<"bug"<<endl;
#define read(x) scanf("%d",&x)
using namespace std;
typedef long long ll;

const int MAX_N=2000+2;
const int MOD=1e9+7;
const int INF=0x3f3f3f3f;

vector <int> edge[MAX_N];
int n,cur,cnt,top,mp[MAX_N],DFN[MAX_N],LOW[MAX_N],s[MAX_N];

void tarjan(int u){
    DFN[u]=LOW[u]=cur++;
    s[++top]=u;
    for(int i=0;i<(int)edge[u].size();i++){
        int v=edge[u][i];
        if(!DFN[v]){
            tarjan(v);
            LOW[u]=min(LOW[u],LOW[v]);
        }
        else if(DFN[v] && !mp[v])   LOW[u]=min(LOW[u],DFN[v]);
    }
    if(DFN[u]==LOW[u]){
        int v=-1;
        cnt++;
        while(u!=v){
            v=s[top--];
            mp[v]=cnt;
//            cout << v<<" ";
        }
//        puts("************");
    }
}

int main(void){
    read(n);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            int x;read(x);
            if(i==j)    continue;
            if(x>0) edge[i].push_back(j);
        }
    }
    for(int i=1;i<=n;i++)
        if(!DFN[i]) tarjan(i);
//    cout << cnt << endl;
    if(cnt==1)  cout <<"YES"<<endl;
    else    cout <<"NO"<<endl;
    return 0;
}