bzoj 4753 最佳团体 —— 01分数规划+树形背包

时间：2023-03-09 16:15:51
bzoj 4753 最佳团体 —— 01分数规划+树形背包

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

注意赋初值为 -inf；

eps 设为 1e-3 会 WA ...

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int const xn=;

int n,m,hd[xn],ct,to[xn],nxt[xn],s[xn],w[xn],siz[xn];

double ans,f[xn][xn],eps=1e-,a[xn];

void add(int x,int y){to[++ct]=y; nxt[ct]=hd[x]; hd[x]=ct;}

int rd()

{

    int ret=,f=; char ch=getchar();

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

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

    return f?ret:-ret;

}

void dfs(int x)

{

    f[x][]=a[x]; siz[x]=;

    for(int i=hd[x],u;i;i=nxt[i])

    {

        dfs(u=to[i]);

        for(int j=min(m,siz[x]+siz[u]);j>=;j--)

            for(int k=max(,j-siz[x]);k<j&&k<=siz[u];k++)

                f[x][j]=max(f[x][j],f[u][k]+f[x][j-k]);

        siz[x]+=siz[u];

    }

}

bool ck(double k)

{

    for(int i=;i<=n;i++)a[i]=1.0*w[i]-1.0*s[i]*k;

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

        for(int j=;j<=m;j++)f[i][j]=-1e9;//

    dfs();

    return f[][m]>=;

}

int main()

{

    m=rd()+; n=rd(); double l=,r=;//+1

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

    {

        s[i]=rd(); w[i]=rd(); fa=rd();

        add(fa,i); r+=w[i];

    }

    while(l-r<=eps)

    {

        double mid=(l+r)/;

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

        else r=mid-eps;

    }

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

    return ;

}

相关文章