HUSTOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs ContestProblemSetList
Login Register

问题 C: 挖地雷(noip原题)

内存限制：128 MB 时间限制：1.000 S 标准输入输出
题目类型：传统 评测方式：文本比较 上传者：
提交：111 通过：40
返回比赛提交提交记录

题目描述

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

输入格式

【输入格式】
    N                                             //地窖的个数
    W1，W2，……WN                   //每个地窖中的地雷数
    X1，Y1                                   //表示从X1可到Y1
    X2，Y2
    ……
   0，0 


输出格式

【输出格式】
    K1-K2-…-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

分类标签