B3611 【模板】传递闭包——题解

解题思路

使用 Floyd 的布尔形式。枚举中转点 $k$，若当前已知 $i$ 能到 $k$ 且 $k$ 能到 $j$，就把 $i$ 到 $j$ 标为可达。按 $k=1\ldots n$ 依次加入可用中转点后，矩阵即为传递闭包。

复杂度分析

时间复杂度 $O(n^3)$，空间复杂度 $O(n^2)$。

C++17 参考代码

#include <bits/stdc++.h>
using namespace std;
int a[105][105];
int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n; cin>>n;
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>a[i][j];
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++) if(a[i][k])
            for(int j=1;j<=n;j++) if(a[k][j]) a[i][j]=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++) cout<<a[i][j]<<(j==n?'\n':' ');
    }
    return 0;
}

#include <bits/stdc++.h> using namespace std; int a[105][105]; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin>>n; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>a[i][j]; for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) if(a[i][k]) for(int j=1;j<=n;j++) if(a[k][j]) a[i][j]=1; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++) cout<<a[i][j]<<(j==n?'\n':' '); } return 0; }