#P4753. [Jsoi2016]最佳团体

    ID: 3873 传统题 1000ms 512MiB 尝试: 2115 已通过: 521 难度: 7 上传者: 标签>难度分类提高排序与序列处理二分答案实数二分动态规划依赖背包树算法DFS 序子树转区间DAG 动态规划CF2200杂项

[Jsoi2016]最佳团体

[JSOI2016] 最佳团体

题目描述

JSOI 信息学代表队一共有 NN 名候选人,这些候选人从 11 到 NN 编号。方便起见,JYY 的编号是 00 号。每个候选人都由一位编号比他小的候选人RiR_i 推荐。如果 Ri=0R_i = 0,则说明这个候选人是 JYY 自己看上的。

为了保证团队的和谐,JYY 需要保证,如果招募了候选人 ii,那么候选人 RiR_i 也一定需要在团队中。当然了,JYY 自己总是在团队里的。每一个候选人都有一个战斗值 PiP_i ,也有一个招募费用 SiS_i 。JYY 希望招募 KK 个候选人(JYY 自己不算),组成一个性价比最高的团队。也就是在恰好选择 KK 位候选人的所有合法团队中,最大化总战斗值与总招募费用之比。

输入格式

输入一行包含两个正整数 KK 和 NN 。

接下来 NN 行,其中第 ii 行包含三个整数 SiS_i , PiP_i , RiR_i , 表示候选人 ii 的招募费用,战斗值和推荐人编号。

输出格式

输出一行一个实数,表示最佳比值。答案四舍五入到小数点后三位。

样例 #1

样例输入 #1

1 2
1000 1 0
1 1000 1

样例输出 #1

0.001

提示

对于100%的数据满足1≤K≤N≤25001\le K\le N\le 2500,0<Si,Pi≤1040<S_i,P_i\le 10^4 , 0≤Ri<i0\le R_i<i