问题1555--钻石总统(pku3345 Bribing FIPA)1555: 钻石总统(pku3345 Bribing FIPA)
时间限制: 1 Sec 内存限制: 128 MB
提交: 0 解决: 0
[提交] [状态] [讨论版] [命题人:]题目描述
有个人要竞选某职务,有N个国家参选，他想通过贿赂某些国家来赢得这个国家的选票，每个国家都要花费相应的钻石才可以被贿赂。因为国家与国家之间存在着控制关系，付费给某个国家，那么就可以赢得这个国家和它直接或间接控制的所有国家的选票。
其实国家的控制关系可以看成一棵树，对于本题，是给一个森林。
你的任务是如果至少要赢得M个国家的选票，最少要花多少钻石。
输入
3 2 //N ,M 接下来是N行，每行前两个为国家名和贿赂改国家需要的钻石数，后面跟着的是这个国家可以控制的国家名字，可以没有。输入#结束
Aland 10
Boland 20 Aland
Coland 15
#
输出
最后需要的钻石数。
样例输入
3 2
Aland 10
Boland 20 Aland
Coland 15
#
样例输出
20
来源/分类
[提交] [状态]