网站页面
当前课程
成员
常规
第一章 分治算法
第二章 递归算法
第三章 排列组合问题
第四章 高精度算法
第五章 排序算法
第六章 穷举算法
第七章 贪心算法
第八章 递推算法
第九章 搜索算法
第十章 模拟算法
逆转未来
成绩 | 100 | 开启时间 | 2016年05月31日 星期二 11:45 |
折扣 | 0.8 | 折扣时间 | 2016年05月31日 星期二 11:45 |
允许迟交 | 是 | 关闭时间 | 2016年05月31日 星期二 11:45 |
输入文件 | reverse.in | 输出文件 | reverse.out |
【题目描述】逆转未来(reverse.cpp/c/pas)HDU 1561
后世的历史学家始终不明白为什么修罗王在人类文明存亡的生死攸关之际给了天顶星人最后的一击,他们从心理学、阴谋论、人性说等方面提出了种种猜想并为此争论不休。不过我们不必理会他们那些夸夸其谈的酸腐理论,因为全球著名无厘头导演张某某拍摄的搞笑纪录片《宇宙文明终极战──我和天顶星人不得不说的故事》里说得很靠谱:修罗王一定是看上天顶星人的宝物了。他是这样描述的:愚蠢而贪婪的修罗王率领他的邪恶军团攻击由恶心的天顶星人占据的N座城堡,每座城堡都有一定的宝物,但由于地理位置原因,有些城堡不能直接攻克,要攻克这些城堡必须先攻克其他某一个特定的城堡。你能帮修罗王算出要获得尽量多的宝物应该攻克哪M个城堡吗?
【输入格式】
每个测试实例首先包括2个整数,N,M。(1 ≤ M ≤ N ≤ 200);在接下来的N行里,每行包括2个整数a,b。在第 i 行,a 代表要攻克第 i 个城堡必须先攻克第 a 个城堡,如果 a = 0 则代表可以直接攻克第 i 个城堡。b 代表第 i 个城堡的宝物数量,b ≥ 0。当N = 0, M = 0输入结束。
【输出格式】
对于每个测试实例,输出一个整数,代表攻克M个城堡所获得的最多宝物的数量。
【输入样例】
3 2
0 1
0 2
0 3
7 4
2 2
0 1
0 4
2 1
7 1
7 6
2 2
0 0
【输出样例】
5
13