A22695.最佳团体
省选/NOI-
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
JSOI 信息学代表队一共有 N 名候选人,这些候选人从 1 到 N 编号。方便起见,JYY 的编号是 0 号。每个候选人都由一位编号比他小的候选人Ri 推荐。如果 Ri=0,则说明这个候选人是 JYY 自己看上的。
为了保证团队的和谐,JYY 需要保证,如果招募了候选人 i,那么候选人 Ri 也一定需要在团队中。当然了,JYY 自己总是在团队里的。每一个候选人都有一个战斗值 Pi ,也有一个招募费用 Si 。JYY 希望招募 K 个候选人(JYY 自己不算),组成一个性价比最高的团队。也就是,这 K 个被 JYY 选择的候选人的总战斗值与总招募费用的比值最大。
输入格式
输入一行包含两个正整数 K 和 N 。
接下来 N 行,其中第 i 行包含三个整数 Si , Pi , Ri ,
表示候选人 i 的招募费用,战斗值和推荐人编号。
输出格式
输出一行一个实数,表示最佳比值。答案保留三位小数。
输入输出样例
输入#1
1 2 1000 1 0 1 1000 1
输出#1
0.001
说明/提示
对于100%的数据满足1≤K≤N≤2500,0<Si,Pi≤104 ,
0 ≤ Ri < i