bzoj 4753 [Jsoi2016]最佳团体——0/1分数规划

时间：2021-02-02 08:22:22

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=4753

0/1分数规划裸题。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define db double

using namespace std;

const int N=;

const db eps=1e-,INF=1e8;

int n,k,s[N],p[N],hd[N],xnt,to[N],nxt[N],siz[N];

db ans,l,r,mid,a[N],dp[N][N];

int rdn()

{

    int ret=;bool fx=;char ch=getchar();

    while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}

    while(ch>=''&&ch<='') ret=(ret<<)+(ret<<)+ch-'',ch=getchar();

    return fx?ret:-ret;

}

void add(int x,int y)

{

    to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;

}

void dfs(int cr)

{

    dp[cr][]=a[cr]; siz[cr]=;

    for(int j=;j<=k;j++) dp[cr][j]=-INF;

    for(int i=hd[cr],v;i;i=nxt[i])

    {

        dfs(v=to[i]);

        for(int j=min(k,siz[cr]+siz[v]);j>=;j--)

            for(int l=max(,j-siz[cr]);l<=siz[v]&&l<j;l++)

                dp[cr][j]=max(dp[cr][j],dp[v][l]+dp[cr][j-l]);

        siz[cr]+=siz[v];

    }

}

bool check()

{

    for(int i=;i<=n;i++)

        a[i]=p[i]-s[i]*mid;

    dfs();

    return dp[][k]>=;

}

int main()

{

    k=rdn()+; n=rdn();

    for(int i=,d;i<=n;i++)

    {

        s[i]=rdn(); p[i]=rdn();

        d=rdn(); add(d,i); r+=p[i];

    }

    for(int i=;i<=n;i++) dp[i][]=-INF;

    while(r-l>eps)

    {

        mid=(l+r)/;

        if(check()) ans=mid,l=mid+eps;

        else r=mid-eps;

    }

    printf("%.3lf\n",ans);

    return ;

}

相关文章