做题网站推荐: OpenJudge VIJOS UOJ CF JOYOI CODEVS 洛谷 RQNOJ BZOJ POJ HDU

本站题目推荐: 高精度 模拟 排序 递推 贪心 递归 搜索 动态规划 数学 图论 数据结构 实名认证 卡评测举报

输入输出 变量类型 顺序结构 选择结构 循环结构 一维数组 NOIP 资源下载


问题 2141. -- 宝典2第十一章鸿门宴

2141: 宝典2第十一章鸿门宴

时间限制: 1 Sec  内存限制: 128 MB
提交: 4  解决: 3
[上一题][提交][讨论版][状态][下一题]

题目描述

【问题描述】鸿门宴(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

输入

输出

提示

标签

[上一题][提交][讨论版][状态][下一题]