Strictly Positive Matrix

wjh15101051's space

卧薪尝胆，厚积薄发。

Date: Sun Jul 08 21:25:45 CST 2018

In Category: NoCategory

Description：

给一个所有元素非负，且主对角线元素和 $>0$ 的矩阵 $A$ ，问是否存在一个数 $k$ 使得 $A^k$ 所有元素为正。

$1\le n \le 2000$

Solution：

把 $A$ 看作有向图邻接矩阵，主对角线非负代表至少存在一个自环， $A^k$ 所有元素非负即为走 $k$ 步任意两对点能互相到达。跑 $tarjan$ 判是否强连通即可。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<stack>

#include<cstring>

using namespace std;

int n;

#define MAXN 2010

struct edge

{

	int to,nxt;

}e[MAXN * MAXN * 2];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	++edgenum;e[edgenum].to = b;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	return;

}

stack<int> s;

int dfn[MAXN],low[MAXN],tot = 0;

bool v[MAXN];

int scc = 0;

void tarjan(int k)

{

	dfn[k] = low[k] = ++tot;

	s.push(k);v[k] = true;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(dfn[e[i].to] == 0)

		{

			tarjan(e[i].to);

			low[k] = min(low[k],low[e[i].to]);

		}

		else if(v[e[i].to])

		{

			low[k] = min(low[k],dfn[e[i].to]); 

		}

	}

	if(low[k] >= dfn[k])

	{

		++scc;

		int t;

		do

		{

			t = s.top();s.pop();

			v[t] = false;

		}while(t != k);

	}

	return;

}

int main()

{

	scanf("%d",&n);

	int a;

	for(int i = 1;i <= n;++i)

	{

		for(int j = 1;j <= n;++j)

		{

			scanf("%d",&a);

			if(a > 0)add(i,j);

		}

	}

	for(int i = 1;i <= n;++i)

	{

		if(dfn[i] == 0)tarjan(i);

	}

	if(scc == 1)puts("YES");

	else puts("NO");

	return 0;

}

In tag: 图论-连通性-tarjan

wjh15101051