跳到主要内容
图灵 OJTURING / ONLINE JUDGE

#F0165. #2071. 「JSOI2016」最佳团体

  • ID: 171
  • 传统题
  • 1000ms
  • 256MiB
  • 尝试: 0
  • AC · 已通过: 0
  • 教学难度:待分级
  • 上传者:
  • 待分类
  • 整理状态
  • 难度待定
  • 难度
  • 共享题库
  • LibreOJ
  • 中文题面
  • 题目来源
  • 题面语言

#2071. 「JSOI2016」最佳团体

题目描述

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

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

输入格式

输入一行包含两个正整数 和 。
接下来 行,其中第 行包含三个整数 表示候选人 的招募费用,战斗值和推荐人编号。

输出格式

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

样例

样例输入

1 2
1000 1 0
1 1000 1

样例输出

0.001

数据范围与提示

对于 的数据满足 。


题目来源:fps-loj-small-pics.zip;FPS 共享题包,题包内第 48 题。保留原作者与原赛事署名。