网站页面
当前课程
成员
常规
第一章 分治算法
第二章 递归算法
第三章 排列组合问题
第四章 高精度算法
第五章 排序算法
第六章 穷举算法
第七章 贪心算法
第八章 递推算法
第九章 搜索算法
第十章 模拟算法
宝藏
成绩 | 100 | 开启时间 | 2016年05月31日 星期二 10:45 |
折扣 | 0.8 | 折扣时间 | 2016年05月31日 星期二 10:45 |
允许迟交 | 是 | 关闭时间 | 2016年05月31日 星期二 10:45 |
输入文件 | mine.in | 输出文件 | mine.out |
【题目描述】宝藏(mine.cpp/c/pas)RQNOJ 30
天顶星人与魔法世界的战争可以追溯到远古时代,这就是传说中的“神话时代”又称“众神陨落时代”。这场星际战争毁灭了人类创造的大部分科技文明,当时幸存的人类为了保存文明的火种,在地下建造了一个神秘的宝藏,该宝藏是没有出口,只有入口,现在修罗王在与天顶星人的接触中查到了宝藏的线索,知道宝藏总共有N个分岔口,在分岔口处是有科技源的,每个科技源都有一个价值。他偷偷带领了M个人来挖宝藏,为了安全起见,在每个分岔口必须至少留一个人下来,这个留下来的人可以挖科技源(每个人只能挖一个地方的科技源),这样才能保证不会迷路,而且这个迷宫有个特点,任意两点间有且只有一条路可通。请问如何才能多挖些科技源回去。
【输入格式】
第1行:两个正整数N,M 。N表示宝藏点的个数,M表示挖宝藏人数。(n≤1000,m≤100)
第2行:N个整数,第i个整数表示第i个宝藏的价值。(保证|wi|<maxint)
第N+2行:两个非负整数A和B,表示A通向B,当A=0,表示A是入口。(保证A,B≤n)
【输出格式】
输出最多挖回的价值。
【样例输入】
4 3
5 6 2 4
1 2
0 1
2 3
3 4
【样例输出】
13