A5536 | $「一本通 3.5 练习 2」消息的传递$

时间限制1s

内存限制512MB

通过 / 提交0/0

题目描述

我们的郭嘉大大在曹操这过得逍遥自在，但是有一天曹操给了他一个任务，在建邺城内有 $N$ 个袁绍的奸细，将他们从 $1$ 到 $N$ 进行编号，同时他们之间存在一种传递关系，即若$C_{i,j}=1$，则奸细 $i$ 能将消息直接传递给奸细 $j$。 现在曹操要发布一个假消息，需要传达给所有奸细，而我们的郭嘉大大则需要传递给尽量少的奸细使所有的奸细都知道这一个消息，问我们至少要传给几个奸细？

文件的第一行为 $N$，第二行至第 $N+1$ 行为 $N \times N$ 的矩阵（若第 $I$ 行第 $J$ 列为 $1$，则奸细 $I$ 能将消息直接传递给奸细 $J$，若第 $I$ 行第 $J$ 列为 $0$，则奸细 $I$ 不能将消息直接传递给奸细 $J$）。

输出文件只有一行：即我们的郭嘉大大首先至少要传递的奸细个数。

输入 #1

8
0 0 1 0 0 0 0 0
1 0 0 1 0 0 0 0
0 1 0 1 1 0 0 0
0 0 0 0 0 1 0 0
0 0 0 1 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 1 0 0 0 1
0 0 0 0 0 0 1 0

输出 #1

C++ 编辑器

输入

输出