BZOJ4753: [Jsoi2016]最佳团体

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

应该是比较裸的题目

01分数规划+树形依赖背包。

01分数规划的话按照套路二分检验,注意设置好精度

树形依赖背包注意在枚举的时候上限应该在枚举之后更改否则会被卡成O(N^3\log ans)

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=1e6+10,INF=1e4+10;
inline char nc()
{
    static char buf[MAXN],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
    char c=nc();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=nc();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=nc();}
    return x*f;
}
int N,K;
int S[MAXN],P[MAXN],R[MAXN];
struct node
{
    int u,v,nxt;
}edge[MAXN];
int head[MAXN];
int num=1;
inline void AddEdge(int x,int y)
{
    edge[num].u=x;
    edge[num].v=y;
    edge[num].nxt=head[x];
    head[x]=num++;
}
double dp[2501][2501],/*i处,选了j个*/siz[MAXN],w[MAXN];
void find(int now)
{
    siz[now]=1;
    for(int i=head[now];i!=-1;i=edge[i].nxt)
        find(edge[i].v),siz[now]+=siz[edge[i].v];
}
void dfs(int now)
{
    int tot=0,b=0;
    if(now) dp[now][1]=w[now],tot=1,b++;
    else dp[now][0]=0;
    for(int i=head[now];i!=-1;i=edge[i].nxt)
    {
        dfs(edge[i].v);
        for(int j=tot;j>=b;j--)//背包容量 
            for(int k=1;k<=siz[edge[i].v];k++)
                dp[now][j+k]=max(dp[now][j+k],dp[now][j]+dp[edge[i].v][k]);
        tot+=siz[edge[i].v];//必须在后面加 
    }
}
bool check(double val)
{
    memset(dp,0xc2,sizeof(dp));
    for(int i=1;i<=N;i++) w[i]=P[i]-val*S[i];
    dfs(0);
    return dp[0][K]>=0;
}
int main()
{
    #ifdef WIN32
    freopen("a.in","r",stdin);
    #else 
    #endif
    memset(head,-1,sizeof(head));
    K=read(),N=read();
    for(int i=1;i<=N;i++)
    {
        S[i]=read(),P[i]=read(),R[i]=read();
        AddEdge(R[i],i);
    }
    find(0);
    double l=0,r=INF;
    double ans=0;
    while(r-l>1e-5)
    {
        double mid=(l+r)/2;
        if(check(mid)) l=mid;
        else r=mid;    
    }
    printf("%.3lf",(l+r)/2);
     return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Crossin的编程教室

【每周一坑】田忌赛马

本周的题目取自著名的历史典故:田忌赛马 背景资料如下 田忌经常与齐国众公子赛马,设重金赌注。田忌的上宾孙膑发现他们的马脚力都差不多,马分为上、中、下三等,于是对...

30210
来自专栏数据结构与算法

洛谷P1450 [HAOI2008]硬币购物

题目描述 硬币购物一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西,去了tot次。每次带di枚ci硬币,买si的价值的东西。请问每次有多少种付...

2604
来自专栏微信公众号:Java团长

Java打飞机小游戏(附完整源码)

技术源于分享,所以今天抽空把自己之前用java做过的小游戏整理贴出来给大家参考学习。java确实不适合写桌面应用,这里只是通过这个游戏让大家理解oop面向对象编...

1.1K2
来自专栏企鹅号快讯

数控铣床编程实例 数控铣床操作详解

数控铣床操作详解 实例一 ? 毛坯为70㎜×70㎜×18㎜板材,六面已粗加工过,要求数控铣出如图2-23所示的槽,工件材料为45钢。 根据图样要求、毛坯及前道工...

4237
来自专栏逸鹏说道

临时处理小记:把Numpy的narray二进制文件转换成json文件

临时处理一个Numpy的二进制文件,分析知道里面是dict类型,简单小记一下,如果Numpy和Python基础不熟悉可以看我之前写的文章(贴一下Numpy的)

1343
来自专栏owent

POJ PKU Let's Go to the Movies 解题报告

题目链接:http://acm.pku.edu.cn/JudgeOnline/problem?id=3513

852
来自专栏Python小屋

Python使用numpy和pandas模拟转盘抽奖游戏

之前写过一个类似的代码,不过都是用的Python内置对象,详见几行Python代码模拟轮盘抽奖游戏,本文再提供一个使用numpy和pandas实现的代码。 问题...

3658
来自专栏逍遥剑客的游戏开发

UE4中程序驱动的LookAt动画

4228
来自专栏海天一树

NOIP 2011初赛普及组C/C++答案详解

3 C 8G = 8 * 1024 M 8 * 1024 / 2 = 4096张 注意,题目说的是“大约”,不要求精确。

1382
来自专栏desperate633

LeetCode 134. Gas Station题目分析

There are N gas stations along a circular route, where the amount of gas at stat...

1014

扫码关注云+社区

领取腾讯云代金券