网站页面
当前课程
成员
常规
第一章 分治算法
第二章 递归算法
第三章 排列组合问题
第四章 高精度算法
第五章 排序算法
第六章 穷举算法
第七章 贪心算法
第八章 递推算法
第九章 搜索算法
第十章 模拟算法
鸿门宴
成绩 | 100 | 开启时间 | 2016年05月31日 星期二 11:30 |
折扣 | 0.8 | 折扣时间 | 2016年05月31日 星期二 11:30 |
允许迟交 | 是 | 关闭时间 | 2016年05月31日 星期二 11:30 |
输入文件 | party.in | 输出文件 | party.out |
【问题描述】鸿门宴(party.cpp/c/pas)TOJ 1039
修罗王欲瘫痪天顶星人军队的建制,于是设计邀请天顶星人军官在一个城堡参加一场盛大的晚会。他的借口是为了让到会的每个人不受他的直接上司约束而能玩得开心,所以晚会的安排是:如果邀请了某个人,那么一定不会再邀请他的直接的上司,但该人的上司的上司,上司的上司的上司……都可以邀请。已知每个人最多有唯一的一个上司。
已知每个参加晚会的天顶星人都有一定的价值,求一个邀请方案,使价值的和最大。
【输入格式】
第1行一个整数N(1≤N≤6000)表示天顶星人的人数。
接下来N个整数。表示第i个人的价值x(-128≤x≤127)。
接下来每行两个整数L,K。表示第K个人是第L个人的上司。
输入以0 0结束。
【输出格式】
一个数,最大的价值和。
【样例输入】
7
1 1 1 1 1 1 1
1 3
2 3
6 4
7 4
4 5
3 5
0 0
【样例输出】
5