「JSOI2016」最佳团体-树上背包+0/1分数规划

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 选择的候选人的总战斗值与总招募费用的比值最大。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×