问题 1317 --DP基础——挖地雷

1317: DP基础——挖地雷★★★★

时间限制: 1 Sec  内存限制: 128 MB
提交: 493  解决: 355
[提交][状态][命题人:]

题目描述

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


输入

N                                          //地窖的个数

W1,W2,……WN                                                             //每个地窖中的地雷数

X1,Y1                                     //表示从X1可到Y1

X2,Y2

……

0,0                                       //表示输入结束

输出

K1-K2-…-Kv                                //挖地雷的顺序

MAX                                        //最多挖出的地雷数

样例输入
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

提示

来源

 

[提交][状态]