【模板】传递闭包

Luogu

IDLGB3611

Time1000ms

Memory128MB

DifficultyP3

图论bitsetFloyd 算法模板题

给定一张点数为 $n$ 的有向图的邻接矩阵，图中不包含自环，求该有向图的传递闭包。一张图的邻接矩阵定义为一个 $n\times n$ 的矩阵 $A=(a_{ij})_{n\times n}$，其中 $$ a_{ij}=\left\{ \begin{aligned} 1,i\ 到\ j\ 存在直接连边\\ 0,i\ 到\ j\ 没有直接连边 \\ \end{aligned} \right. $$ 一张图的传递闭包定义为一个 $n\times n$ 的矩阵 $B=(b_{ij})_{n\times n}$，其中 $$ b_{ij}=\left\{ \begin{aligned} 1,i\ 可以直接或间接到达\ j\\ 0,i\ 无法直接或间接到达\ j\\ \end{aligned} \right. $$ ## Input 输入数据共 $n+1$ 行。第一行一个正整数 $n$。第 $2$ 到 $n+1$ 行每行 $n$ 个整数，第 $i+1$ 行第 $j$ 列的整数为 $a_{ij}$。 ## Output 输出数据共 $n$ 行。第 $1$ 到 $n$ 行每行 $n$ 个整数，第 $i$ 行第 $j$ 列的整数为 $b_{ij}$。 [samples] ## Note 对于 $100\%$ 的数据，$1\le n\le 100$，保证 $a_{ij}\in\{0,1\}$ 且 $a_{ii}=0$。

Samples

Input #1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "【模板】传递闭包",
    "description": {
      "content": "给定一张点数为 $n$ 的有向图的邻接矩阵，图中不包含自环，求该有向图的传递闭包。 一张图的邻接矩阵定义为一个 $n\\times n$ 的矩阵 $A=(a_{ij})_{n\\times n}$，其中 $$ a_{ij}=\\left\\{ \\begin{aligned} 1,i\\ 到\\ j\\ 存在直接连边\\\\ 0,i\\ 到\\ j\\ 没有直接连边 \\\\ \\end{aligned} \\right. $",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB3611"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定一张点数为 $n$ 的有向图的邻接矩阵，图中不包含自环，求该有向图的传递闭包。\n\n一张图的邻接矩阵定义为一个 $n\\times n$ 的矩阵 $A=(a_{ij})_{n\\times n}$，其中\n\n$$ a_{ij}=\\left\\{\n\\begin{aligned}\n1,i\\ 到\\ j\\ 存在直接连边\\\\\n0,i\\ 到\\ j\\ 没有直接连边 \\\\\n\\end{aligned}\n\\right.\n$...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments