#4753. [JSOI2016] 最佳团体

[JSOI2016] 最佳团体

题目描述

JSOI 信息学代表队一共有 nn 名候选人,这些候选人从 11nn 编号。方便起见,JYY 的编号是 00 号。每个候选人都由一位编号比他小的候选人 rir_i 推荐。如果 ri=0r_i=0 则说明这个候选人是 JYY 自己看上的。为了保证团队的和谐,JYY 需要保证,如果招募了候选人 ii,那么候选人 rir_i 也一定需要在团队中。当然了,JYY 自己总是在团队里的。每一个候选人都有一个战斗值 pip_i,也有一个招募费用 sis_i。JYY 希望招募 kk 个候选人(JYY 自己不算),组成一个性价比最高的团队。也就是,这 kk 个被 JYY 选择的候选人的总战斗值与总招募总费用的比值最大。

输入格式

输入一行包含两个正整数 kknn

接下来 nn 行,其中第 ii 行包含 33 个整数 si,pi,ris_i,p_i,r_i 表示候选人 ii 的招募费用,战斗值和推荐人编号。

输出格式

输出一行一个实数,表示最佳比值。答案保留三位小数。

1 2
1000 1 0
1 1000 1
0.001

数据规模与约定

对于 100%100\% 的数据,1kn2.5×1031\le k\le n\le 2.5\times 10^30<si,pi1040<s_i,p_i\le10^40ri<i0\le r_i<i

题目来源

没有写明来源。