CF402E Strictly Positive Matrix(Tarjan&思维)题解

发布于 2021-10-19  48 次阅读


Updated On 2021.10.19:修好了挂掉的 $\LaTeX$。

Updated On 2021.11.4:修改了一处笔误以及部分格式的错误,感谢评论区 LawrenceSivan 同学的指正。

这个题十分巧妙,现存题解又大多各有模糊不清之处,所以我来补一份题解吧。

题目大意

给出一个矩阵 $A$,问是否存在一个正整数 $k$ 使得 $A^k$ 的所有元素都是正数。

$2 \le n \le 2000$,$0 \le a_{i,j} \le 50$,$\sum_{i=1}^{n} a_{i,i}>0$。

解题思路

妙,太妙了。

首先,我们发现题目只要求所有元素为严格正数,也就是我们只关心这是不是 $>0$,而不关心具体的值是多少。所以我们可以想到把原矩阵中 $>0$ 的值都视作 $1$

为啥这么做是对的呢?我们考虑矩阵乘法的式子是 $a_{i,j}=\sum_{k=1}^{n} b_{i,k} \times c_{k,j}$,也就是只要一组 $b_{i,k}$ 与 $c_{k,j} $ 的值 $>0$,最后值就 $>0$。而 $>0$ 这个性质,$1$ 与其他正数是完全等价的。

然后我们就把原矩阵变成了一个 $01$ 矩阵。这玩意儿像啥呢?是不是像极了图论中的邻接矩阵

更进一步,我们还是观察矩阵乘法的性质,$a_{i,j}=\sum_{k=1}^{n} b_{i,k} \times c_{k,j}$ 这玩意儿是不是像极了 Floyd 算法的转移

不如我们来说得更清晰一点。为了方便阅读,我们用 $A[k]$ 代表 $A^k$。

那么在矩阵中,$A[k]=A[k-1] \times A[1]$。 转化成图论形式,就是$A[k]{i,j}=\bigvee{x=1}^n A[k-1]{i,x} \& A[1]{x,j}$。

看起来好像很复杂,实际上意义就是枚举中间点 $x$,如果 $i$ 到 $x$ 有一条长为 $k-1$ 的路径,并且 $x$ 到 $j$ 有一条长为 $1$ 的路径,那么 $i$ 到 $j$ 就有一条长为 $k$ 的路径。原来矩阵乘法的乘号被我们用 $\&$ 符号代替,$\sum$ 符号被我们用 $\bigvee$ ($or$)符号代替,并且你会发现这简直是天衣无缝。

那么问题就转化为了给定一个邻接矩阵,要求是否存在一个 $k$ 使得其所有点之间都存在长度为 $k$ 的路径。

看起来好像很难下手。此时我们就需要用到题目中的另一个性质:$\sum_{i=1}^{n} a_{i,i}>0$。也就是说,图中至少存在一个自环

那就好办了,只要在原图中 $x$ 可以到达 $y$,那我们就可以把 $k$ 设置得很大(目的是为了大于 $x$ 到 $y$ 的最短路),然后通过不断走自环来抵消多余的步数

此时我们就会发现,问题已经被我们转化成了判断一个图是不是任意两点都互相可达

这玩意儿就是 $tarjan$ 裸题了。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=100005,M=4000005;

struct Edge{
    int vet,nxt;
}e[M];

int n,edge=0,head[N];
int low[N],dfn[N],timer=0;
int sta[N],top=0,cnt=0;
bool insta[N];

inline int read(){
    int x=0,f=1; char ch=getchar();
    while (!isdigit(ch)){ if (ch=='-') f=-1; ch=getchar(); }
    while (isdigit(ch)){ x=x*10+ch-'0'; ch=getchar(); }
    return x*f;
}

inline int gmin(const int& x,const int& y){ return x < y ? x : y; }
inline int gmax(const int& x,const int& y){ return x > y ? x : y; }

inline void addedge(int x,int y){
    e[++edge].vet=y;
    e[edge].nxt=head[x];
    head[x]=edge;
}

void tarjan(int x){
    dfn[x]=low[x]=++timer;
    sta[++top]=x; insta[x]=true;
    for (int i=head[x];i;i=e[i].nxt){
        int v=e[i].vet;
        if (!dfn[v]){
            tarjan(v);
            low[x]=gmin(low[x],low[v]);
        }
        else if (insta[v]) low[x]=gmin(low[x],dfn[v]);
    }
    if (low[x]==dfn[x]){
        ++cnt;
        while (sta[top]!=x) insta[sta[top--]]=false;
        insta[sta[top--]]=false;
    }
}

int main(){
    //freopen("CF402E.in","r",stdin);
    //freopen("CF402E.out","w",stdout);
    n=read();
    for (int i=1;i<=n;++i)
        for (int j=1;j<=n;++j){
            if (read()) addedge(i,j);
        }
    for (int i=1;i<=n;++i)
        if (!dfn[i]) tarjan(i);
    printf((cnt==1) ? ("YES\n") : ("NO\n"));
    return 0;
}

我们无法选择过去,但我们可以改变未来。