http://codeforces.com/problemset/problem/402/E

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

 

题意：給定一个矩阵a，满足a(i,j)>=0且a(i,i)>0。问是否存在k，使得a^k的每一个元素都大于0。

思路：把给定矩阵当作一个邻接矩阵，a(i,j)表示有向边i->j的边权。

如果a是0/1矩阵，那么a^k的任一元素a(i,j)表示从i到j恰好经过k条边可达的方案数。

如果想要详细了解，2008国家集训队论文：俞华程《矩阵乘法在信息学中的应用》，这篇太好了，信息量太大，我有时间再看。

对于这道题，a(i,i)>0说明i->i有自环，题目等价于是否图中任意两点均可达。

用floyd当然方便，但是复杂度承受不了。

只需要知道图中任意两点是否可达，即整个图是不是强连通图，用线性的tarjan即可。

为什么floyd的复杂度高出那么多呢？floyd可以找出任意两点的最短路，过大的信息量对于本题太多冗余，本题只需要知道是否任意两点可达，即是不是强连通图。

#include<bits/stdc++.h>
using namespace std;
#define maxn 3000

int n;
vector<int> G[maxn];
int pre[maxn],lowlink[maxn],sccno[maxn],dfs_clock,scc_cnt;
stack<int> s;

void dfs(int u)
{
	pre[u]=lowlink[u]=++dfs_clock;
	s.push(u);
	for(int i=0;i<G[u].size();i++)
	{
		int v=G[u][i];
		if(!pre[v])
		{
			dfs(v);
			lowlink[u]=min(lowlink[u],lowlink[v]);
		}
		else if(!sccno[v])
		{
			lowlink[u]=min(lowlink[u],pre[v]);
		}
	}
	if(lowlink[u]==pre[u])
	{
		scc_cnt++;
		if(scc_cnt==2){puts("NO");exit(0);}
		for(;;)
		{
			int x=s.top();s.pop();
			sccno[x]=scc_cnt;
			if(x==u)break;
		}
	}
}

void find_scc()
{
	for(int i=1;i<=n;i++)if(!pre[i])dfs(i);
}

int main()
{
	//freopen("input.in","r",stdin);
	int x;
	cin>>n;
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)
	{
		scanf("%d",&x);
		if(x)G[i].push_back(j);
	}
	find_scc();
	for(int i=1;i<=n;i++)if(sccno[i]!=sccno[1]){puts("NO");exit(0);}
	puts("YES");exit(0);
}