Description
JSOI信息学代表队一共有N名候选人,这些候选人从1到N编号。方便起见,JYY的编号是0号。每个候选人都由一位
编号比他小的候选人Ri推荐。如果Ri=0则说明这个候选人是JYY自己看上的。为了保证团队的和谐,JYY需要保证,
如果招募了候选人i,那么候选人Ri”也一定需要在团队中。当然了,JYY自己总是在团队里的。每一个候选人都有
一个战斗值Pi”,也有一个招募费用Si”。JYY希望招募K个候选人(JYY自己不算),组成一个性价比最高的团队。
也就是,这K个被JYY选择的候选人的总战斗值与总招募总费用的比值最大。
Input
输入一行包含两个正整数K和N。
接下来N行,其中第i行包含3个整数Si,Pi,Ri表示候选人i的招募费用,战斗值和推荐人编号。
对于100%的数据满足1≤K≤N≤2500,0<“Si,Pi”≤10^4,0≤Ri<i
Output
输出一行一个实数,表示最佳比值。答案保留三位小数。
Sample Input
1 2

1000 1 0

1 1000 1
Sample Output
0.001

HINT
2017.9.12新加数据一组 By GXZlegend

Source

分数规划+dfs序 背包 常数大 差点被卡T

二分答案 然后结果就是sigma p[x]-s[x]*mid

设dp[i][j]表示i子树选了j个点的最大代价

具体可上网搜索 依赖型背包

只要看选k个能否>0即可

 


elijahqi

退役了 现在在商院 偶尔打CF,有时有ACM regional也去玩一下

发表评论