NOIP1996找雷

2013年11月6日2,6650

题目描述

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

输入

[输入]
 N {地窖的个数}
 W1,W2,……WN    每个地窖中的地雷数} {
 X1,Y1     {表示从X1可到Y1}
 X2,Y2
……
0,0           {表示输入结束}

输出

[输出]
 K1-K2-k3  …… -Kv   {挖地雷的顺序}
 MAX             {最多挖出的地雷数}

样例输入

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

代码