本文共 1772 字，大约阅读时间需要 5 分钟。
原题是说给你个n乘n的矩阵，问你是否可以存在经过k次矩阵乘法，得到a^k，使得新的矩阵满足 每一个i和j都有 a^k[i][j] > 1。
拿到题目 我先算了一下 a^k[i][j] 在k=2时的情况， 发现 a^k[i][j] = a[i][1] * a[1][j] + a[i][2]*a[2][j] + ... +a[i][n] * a[n][j] 题目要求a^k[i][j] > 0 ；
我就想到首先原矩阵每个a[i][j] >= 0 的条件是给定的，所以对于每一个 a[i][1] * a[1][j] 和 a[i][2]*a[2][j] 都满足 乘号左右>=0 。
经过ACMDIY群中的神牛点拨， 说判一遍强联通就可撸，只要全图的点都在一个强联通分量上，就输出“YES”， 否则是“NO”。
想了一下，回到a^k[i][j] = a[i][1] * a[1][j] + a[i][2]*a[2][j] + ... +a[i][n] * a[n][j] > 0这个方程上，换个角度看a[i][j] 。如果，a[i][j] > 0 就代表有i ->j 的有向边。 a[i][1] * a[1][j] 、 a[i][2]*a[2][j] 、 ...、+a[i][n] * a[n][j] ，就代表是不是可能从点1、2、3、...、n的任意一个点上， 使 点i 可以到点j 。然后一旦a^k[i][j] 为正数后，它就在k+1等之后总会为正数。因为从逻辑上可以说，点i已经可以到达j了，这个是性质是可以不受k 值大小影响 而一直传递下去的。
所以只要判断全图是不是一个强联通分量。用tarjan就能撸了。
源代码：
#include#include #include using namespace std;const int V = 2100;vector vec[V];int id[V], pre[V], low[V], s[V], stop, cnt, scnt;void tarjan(int v, int n){ int t, minc = low[v] = pre[v] = cnt++; vector ::iterator pv; s[stop++] = v; for(pv = vec[v].begin(); pv != vec[v].end(); ++pv) { if(-1 == pre[*pv]) tarjan(*pv, n); if(low[*pv] < minc) minc = low[*pv]; } if(minc < low[v]) { low[v] = minc; return; } do { id[t = s[--stop]] = scnt; low[t] = n; } while(t != v); ++scnt;}int main(){ int n, v; scanf("%d", &n); for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) { scanf("%d", &v); if(v != 0) vec[i].push_back(j); } stop = cnt = scnt = 0; for(int i = 0; i < n; i++) pre[i] = -1; for(int i = 0; i < n; ++i) { if(-1 == pre[i]) tarjan(i, n); }// printf("%d\n", scnt); if(scnt == 1) puts("YES"); else puts("NO"); return 0;}
转载地址：http://sbhrb.baihongyu.com/