问题1303--【例9.6】挖地雷

1303: 【例9.6】挖地雷

[命题人 : ]
时间限制 : 1.000 sec  内存限制 : 128 MB

解决: 0提交: 0统计

题目描述

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

输入

第一行：地窖的个数；

第二行：为依次每个地窖地雷的个数；

下面若干行：

xiyi   //表示从xi可到yi，xi<yi。

最后一行为"00"表示结束。

输出

k1−k2−…−kv    //挖地雷的顺序

挖到最多的雷。

样例输入 Copy 

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

样例输出 Copy 

3-4-5-6
34

来源/分类

第二部分基础算法 第九章动态规划 9.1动态规划的基本模型 信息奥赛一本通 
提交