B3611 传递闭包

· · 题解

传递闭包？这是个啥玩意？

通俗地讲，传递闭包就是一个邻接矩阵，表达图连通性的邻接矩阵。要注意的是，在传递闭包里面，如果一个点不在任何一个环中，就规定一个点和自身不连通。

怎么求传递闭包？根据定义，我们发现他需要枚举两个点间是否存在路径。怎么枚举路径？当然要枚举路径上的点。这就让我们自然而然的想到了 Floyd-Warshall 算法。

Floyd-Warshall 运用了动态规划的思想，用 f_{i,j} 表示图上两点间的状态（例如最短路径，连通性等），并枚举中转节点 k 进行转移。转移的大概方式是

f_{i,j}=F(f_{i,k},f_{k,j})

其中 F 是状态转移方程。

在本例中，状态就是连通性，转移过程如下：

  1. 如果 i,j 直接联通，则 f_{i,j}=1
  2. 如果 i,j 不直接连通，但可以通过中转节点 k 连通，则 f_{i,j}=1
  3. 如果枚举了所有中转节点都不能使 i,j 联通，则 f_{i,j}=0

又注意到状态是 0/1 型的，可以用位运算加速。

于是转移方程即为

f_{i,j}=f_{i,j}\operatorname{ or }\ (f_{i,k}\operatorname{and}f_{k,j})

其中 \operatorname{or} 表示按位或运算，\text{and} 表示按位与运算。

这个方程需要预处理直接存在的边。由于这样的边也用 0/1 型的布尔变量表示，可以直接在原图上 DP。

附上完整代码：

#include <bits/stdc++.h>
using namespace std;
inline int read() {
    char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    int x=0;
    while(ch>='0'&&ch<='9') x=(x*10)+(ch^48),ch=getchar();
    return x;
}
inline void write(int x) {
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
inline void wr(int x) {
    write(x);
    putchar(' ');
}
bool mp[105][105];
int n;
void Floyd_Warshall() {
    for(int k=1;k<=n;++k) //注意要先枚举 k，可以自己手玩几个图想一想为什么
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j)
                mp[i][j]|=mp[i][k]&mp[k][j];
}
int main(void) {
    n=read();
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            mp[i][j]=read();
    Floyd_Warshall();
    for(int i=1;i<=n;++i) {
        for(int j=1;j<=n;++j)
            wr(mp[i][j]);
        putchar('\n');
    }
    return 0;
}