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

信息学奥赛题库- 【例9.6】挖地雷

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

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

【题目描述】

在一个地图上有$n$个地窖($n≤200$),每个地窖中埋有一定数量的地雷。同时,给出地窖之间的连接路径,并规定路径都是单向的,且保证都是小序号地窖指向大序号地窖,也不存在可以从一个地窖出发经过若干地窖后又回到原来地窖的路径。某人可以从任意一处开始挖地雷,然后沿着指出的连接往下挖(仅能选择一条路径),当无连接时挖地雷工作结束。设计一个挖地雷的方案,使他能挖到最多的地雷。

【输入】

第一行:地窖的个数;

第二行:为依次每个地窖地雷的个数;

下面若干行:

$x_i;y_i$   //表示从$x_i$可到$y_i$,$x_i<y_i$。

最后一行为”$0;0$”表示结束。

【输出】

$k_1-k_2-…-k_v$    //挖地雷的顺序

挖到最多的雷。

【输入样例】

6
5 10 20 5 4 5
1 2
1 4
2 4
3 4
4 5
4 6
5 6
0 0

【输出样例】

3-4-5-6
34

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