#F. 【模板】传递闭包

A B C D E F G H I J K L M N O P Q R S T U V W
    Type: RemoteJudge 1000ms 256MiB

【模板】传递闭包

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

【模板】传递闭包

题目描述

给定一张点数为 nn 的有向图的邻接矩阵，图中不包含自环，求该有向图的传递闭包。

一张图的邻接矩阵定义为一个 n×nn\times n 的矩阵 A=(aij)n×nA=(a_{ij})_{n\times n}，其中

aij={1,i 到 j 存在直接连边0,i 到 j 没有直接连边a_{ij}=\left\{ \begin{aligned} 1,i\ 到\ j\ 存在直接连边\\ 0,i\ 到\ j\ 没有直接连边 \\ \end{aligned} \right.

一张图的传递闭包定义为一个 n×nn\times n 的矩阵 B=(bij)n×nB=(b_{ij})_{n\times n}，其中

bij={1,i 可以直接或间接到达 j0,i 无法直接或间接到达 jb_{ij}=\left\{ \begin{aligned} 1,i\ 可以直接或间接到达\ j\\ 0,i\ 无法直接或间接到达\ j\\ \end{aligned} \right.

输入格式

输入数据共 n+1n+1 行。

第一行一个正整数 nn。

第 22 到 n+1n+1 行每行 nn 个整数，第 i+1i+1 行第 jj 列的整数为 aija_{ij}。

输出格式

输出数据共 nn 行。

第 11 到 nn 行每行 nn 个整数，第 ii 行第 jj 列的整数为 bijb_{ij}。

样例 #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\% 的数据，1≤n≤1001\le n\le 100，保证 aij∈{0,1}a_{ij}\in\{0,1\} 且 aii=0a_{ii}=0。

北辰OI俱乐部算法提高班：图论专题

Not Claimed
Status
Done
Problem
23
Open Since
2023-11-25 0:00
Deadline
2024-12-31 23:59
Extension
24 hour(s)
  1. About
  2. Contact Us
  3. Privacy
  4. Terms of Service
  5. Copyright Complaint
  6. Language
  7. Legacy mode
  8. Theme
  2. text

  4. 鲁公网安备 37079402001599号

  • 鲁ICP备2022025036号-1
  • Worker 0, 23ms
  • Powered by Hydro v4.9.27 Community