P4322 [JSOI2016]最佳团体

    • 339通过
    • 1.2K提交
  • 题目提供者 ACの666
  • 评测方式 云端评测
  • 标签 2016 江苏
  • 难度 省选/NOI-
  • 时空限制 1000ms / 256MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

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

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

    输入输出格式

    输入格式:

    输入一行包含两个正整数 $K$ 和 $N$ 。

    接下来 $N$ 行,其中第 $i$ 行包含三个整数 $S_i$ , $P_i$ , $R_i$ , 表示候选人 $i$ 的招募费用,战斗值和推荐人编号。

    输出格式:

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

    输入输出样例

    输入样例#1: 复制
    1 2
    1000 1 0
    1 1000 1
    输出样例#1: 复制
    0.001

    说明

    对于100%的数据满足$1≤K≤N≤2500$,$0<S_i,P_i≤10^4$ , $0$ $≤$ $R_i$ $<$ $i$

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。