视频网站代言人,win7电脑做网站服务器,邢台市最新人事调整,多网合一网站平台建设【模板】传递闭包
题目描述
给定一张点数为 n n n 的有向图的邻接矩阵#xff0c;图中不包含自环#xff0c;求该有向图的传递闭包。
一张图的邻接矩阵定义为一个 n n n\times n nn 的矩阵 A ( a i j ) n n A(a_{ij})_{n\times n} A(aij)nn#xff0c;其中 a i…【模板】传递闭包
题目描述
给定一张点数为 n n n 的有向图的邻接矩阵图中不包含自环求该有向图的传递闭包。
一张图的邻接矩阵定义为一个 n × n n\times n n×n 的矩阵 A ( a i j ) n × n A(a_{ij})_{n\times n} A(aij)n×n其中 a i j { 1 , i 到 j 存在直接连边 0 , i 到 j 没有直接连边 a_{ij}\left\{ \begin{aligned} 1,i\ 到\ j\ 存在直接连边\\ 0,i\ 到\ j\ 没有直接连边 \\ \end{aligned} \right. aij{1,i 到 j 存在直接连边0,i 到 j 没有直接连边
一张图的传递闭包定义为一个 n × n n\times n n×n 的矩阵 B ( b i j ) n × n B(b_{ij})_{n\times n} B(bij)n×n其中 b i j { 1 , i 可以直接或间接到达 j 0 , i 无法直接或间接到达 j b_{ij}\left\{ \begin{aligned} 1,i\ 可以直接或间接到达\ j\\ 0,i\ 无法直接或间接到达\ j\\ \end{aligned} \right. bij{1,i 可以直接或间接到达 j0,i 无法直接或间接到达 j
输入格式
输入数据共 n 1 n1 n1 行。
第一行一个正整数 n n n。
第 2 2 2 到 n 1 n1 n1 行每行 n n n 个整数第 i 1 i1 i1 行第 j j j 列的整数为 a i j a_{ij} aij。
输出格式
输出数据共 n n n 行。
第 1 1 1 到 n n n 行每行 n n n 个整数第 i i i 行第 j j j 列的整数为 b i j b_{ij} bij。
样例 #1
样例输入 #1
4
0 0 0 1
1 0 0 0
0 0 0 1
0 1 0 0样例输出 #1
1 1 0 1
1 1 0 1
1 1 0 1
1 1 0 1提示
对于 100 % 100\% 100% 的数据 1 ≤ n ≤ 100 1\le n\le 100 1≤n≤100保证 a i j ∈ { 0 , 1 } a_{ij}\in\{0,1\} aij∈{0,1} 且 a i i 0 a_{ii}0 aii0。 思路
首先读取输入的点数n并定义一个二维布尔数组a[N][N]来存储邻接矩阵。
接着通过两层循环读取邻接矩阵的数据。这里的a[i][j]表示从点i到点j是否存在直接连边。
之后利用Floyd-Warshall算法来求解传递闭包。这个算法的基本思想是对于每一个点k检查所有的点对(i, j)如果点i可以到达点k并且点k可以到达点j那么就可以认为点i可以到达点j。因此有a[i][j] | (a[i][k] a[k][j])。
最后再次通过两层循环输出更新后的邻接矩阵即传递闭包。 AC代码
#include iostream
#define AUTHOR HEX9CF
using namespace std;
using ll long long;const int N 1e3 7;
const int INF 0x3f3f3f3f;
const int MOD 1e9 7;ll n;
bool a[N][N];int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);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) {for (int j 1; j n; j) {a[i][j] | (a[i][k] a[k][j]);}}}for (int i 1; i n; i) {for (int j 1; j n; j) {cout a[i][j] ;}cout \n;}return 0;
}
