最新消息:680元/半年,推荐全网最具性价比的一站式编程学习平台码丁实验室

信息学奥赛题库- 消息的传递

C++ 少儿编程 1114浏览 0评论

友情提示:680元/半年,儿童学编程,就上码丁实验室

【题目描述】

我们的郭嘉大大在曹操这过得逍遥自在,但是有一天曹操给了他一个任务,在建邺城内有 $N$ 个袁绍的奸细,将他们从 $1$ 到 $N$ 进行编号,同时他们之间存在一种传递关系,即若$C_{i,j}=1$,则奸细 $i$ 能将消息直接传递给奸细 $j$。

现在曹操要发布一个假消息,需要传达给所有奸细,而我们的郭嘉大大则需要传递给尽量少的奸细使所有的奸细都知道这一个消息,问我们至少要传给几个奸细?

【输入】

第一行为 $N$,第二行至第 $N+1$ 行为 $N×N$的矩阵(若第 $I$ 行第 $J$ 列为 $1$,则奸细 $I$ 能将消息直接传递给奸细 $J$,若第 $I$ 行第 $J$ 列为 $0$,则奸细 $I$ 不能将消息直接传递给奸细 $J$)。

【输出】

只有一行:即我们的郭嘉大大首先至少要传递的奸细个数。

【输入样例】

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$

您必须 登录 才能发表评论!