{"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$$\n\n一张图的传递闭包定义为一个 $n\\times n$ 的矩阵 $B=(b_{ij})_{n\\times n}$，其中\n\n$$ b_{ij}=\\left\\{\n\\begin{aligned}\n1,i\\ 可以直接或间接到达\\ j\\\\\n0,i\\ 无法直接或间接到达\\ j\\\\\n\\end{aligned}\n\\right.\n$$\n\n## Input\n\n输入数据共 $n+1$ 行。\n\n第一行一个正整数 $n$。\n\n第 $2$ 到 $n+1$ 行每行 $n$ 个整数，第 $i+1$ 行第 $j$ 列的整数为 $a_{ij}$。\n\n## Output\n\n输出数据共 $n$ 行。\n\n第 $1$ 到 $n$ 行每行 $n$ 个整数，第 $i$ 行第 $j$ 列的整数为 $b_{ij}$。\n\n[samples]\n\n## Note\n\n对于 $100\\%$ 的数据，$1\\le n\\le 100$，保证 $a_{ij}\\in\\{0,1\\}$ 且 $a_{ii}=0$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGB3611","tags":["图论","bitset","Floyd 算法","模板题"],"sample_group":[["4\n0 0 0 1\n1 0 0 0\n0 0 0 1\n0 1 0 0","1 1 0 1\n1 1 0 1\n1 1 0 1\n1 1 0 1"]],"created_at":"2026-03-03 11:09:25"}}