2796: 「一本通 3.5 练习 2」消息的传递
Memory Limit:512 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:96
Solved:59
Description
我们的郭嘉大大在曹操这过得逍遥自在,但是有一天曹操给了他一个任务,在建邺城内有 N 个袁绍的奸细,将他们从 1 到 N 进行编号,同时他们之间存在一种传递关系,即若C[i,j]=1,则奸细 i 能将消息直接传递给奸细 j。
现在曹操要发布一个假消息,需要传达给所有奸细,而我们的郭嘉大大则需要传递给尽量少的奸细使所有的奸细都知道这一个消息,问我们至少要传给几个奸细?
Input
文件的第一行为 N,第二行至第 N+1 行为 N×N 的矩阵(若第i 行第 j 列为 1,则奸细 i 能将消息直接传递给奸细 j,若第i行第j 列为 0,则奸细 i 不能将消息直接传递给奸细 j)。
Output
输出文件只有一行:即我们的郭嘉大大首先至少要传递的奸细个数。
HINT
样例输入
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
样例输出
2
N≤1000