CF402E

,

因为有 $a_{i,j}\ge 0$ ，而题目要我们判断的是不是所有点都 $>0$，所以我们可以把所有 $>0$ 的点都看为 $1$。

考虑其图上的意义。若看成 $01$ 的邻接矩阵，则 $A^k$ 表示经过恰好 $k$ 步后整张图是否是一个强连通。

我们可以把 $k$ 想象的很大。因为有：
$$
\sum a_{i,i}>0
$$
说明有自环的存在。问题转化为图是否为强连通。因为可以在这个点上一直绕。

tarjan 判即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 2005
#define put() putchar('\n')
using namespace std;
inline void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
int dfn[maxn],low[maxn],vis[maxn],stac[maxn],tot,sccnum,times;
int a[maxn][maxn],n;
inline void dfs(int x) {
	//printf("%d %d\n",x,sccnum);
	int i;dfn[x]=low[x]=++times;vis[x]=1;stac[++tot]=x;
	for (i=1;i<=n;i++) {
		if (!a[x][i]||i==x) continue;
		if (!dfn[i]) dfs(i),low[x]=min(low[x],low[i]);
		else if (vis[i]) low[x]=min(low[x],dfn[i]);
	}
	if (dfn[x]==low[x]) {
		++sccnum;
		while (1) {
			vis[stac[tot]]=0;
			if (stac[tot--]==x) return;
		}
	}
} 
signed main(void){
    //freopen("1.in","r",stdin);
	int i,j,tot=0;
	read(n);
	for (i=1;i<=n;i++) for (j=1;j<=n;j++) read(a[i][j]);
	for (i=1;i<=n;i++) if (!dfn[i]) dfs(i);
	puts(sccnum==1?"YES":"NO");
    return 0;
}