挖地雷
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
说明
在一个地图上有N个地窖(N<=200),每个地窖中埋有一定数量的地雷。同时,给出地窖之间的连接路径,并规定路径都是单向的,也不存在可以从一个地窖出发经过若干地窖后又回到原来地窖的路径。某人可以从任一处开始挖地雷,然后沿着指出的连接往下挖(仅能选择一条路径),当无连接时挖地雷工作结束。设计一个挖地雷的方案,使他能挖到最多的地雷。
输入格式
第一行一个整数n表示有n个地窖
第二行有n个整数表示每个地窖的地雷数
以下有若干行,每行有两个数x,y表示x可以到y,保证x小于y。
最后一行有两个0,表示输入结束
输出格式
第一行输出挖地雷的顺序。
第二行为最多挖出的地雷数
样例
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