Problem4271--§2 9 【例9.6】挖地雷

4271: §2 9 【例9.6】挖地雷

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

Description

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

Input

第一行:地窖的个数;
第二行为依次每个地窖地雷的个数;
下面若干行:
$x_i\ y_i$  表示从 $x_i$ 可到 $y_i$,$x_i<y_i$。
最后一行为 "$0\ 0$" 表示结束。

Output

$k_1$−$k_2$−$…$−$k_v$   //挖地雷的顺序
挖到最多的雷。
详细看样例输出。

Sample 1 Input

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

Sample 1 Output

3-4-5-6
34

HINT

相同题目:洛谷P2196

Source/Category

基础算法 4.120.动态规划