[CF #236 (Div. 2) E] Strictly Positive Matrix（强联通分量）
浏览数：22 /
时间：2015年06月11日
题目：http://codeforces.com/contest/402/problem/E
题意：给你一个矩阵a，判断是否存在k，使得a^k这个矩阵全部元素都大于0
分析：把矩阵当作01矩阵，超过1的都当作1，那么a矩阵可表示一个有向图的走一次的连通性，则a^k表示有向图走K次的连通性。既然要求最后都没0，即走了K次后，每个点都能互通，这也说明这个图必然是只有一个强联通分量。于是判断k的存在有无，也就是判断a矩阵表示的有向图是不是只有一个强联通分量。
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
