本文共 1608 字，大约阅读时间需要 5 分钟。

每个人有战斗力$p_i$和招募费用$s_i$,现在想招募$k$个人使得$\frac{\sum p_i}{\sum s_i}$最大

同时满足要求若选了$i$那么也必须选择$r_i$

特殊的,如果$r_i=0$,那么没有任何限制

比较明显的树形背包,按照依赖关系由$i$向$r_i$连边

这样定义$f[i][j]$为在$i$的子树中选择$j$个人的最大收益

收益是一个$01$分数规划的形式,设$f(r)=p-k\ast s$

那么二分斜率$k$,作直线$x=k$,如果和某条直线的交点是正数说明答案还可以增加

所以把物品价值看作$p_i-mid\ast s_i$即可

#include 
   
    using namespace std;const int maxn =  3e5+10;const int inf = 1e9;const double eps = 1e-5;struct edge{
       int to,nxt;}d[maxn]; int head[maxn],cnt=1;void add(int u,int v){
       d[++cnt] = ( edge ){
   v,head[u]},head[u] = cnt;}double f[2509][2509],v[maxn],p[maxn],s[maxn];int siz[maxn],n,k,r[maxn];void dfs(int u){
       f[u][1] = v[u]; siz[u] = 1;    for(int i=head[u];i;i=d[i].nxt )    {
           int v = d[i].to;        dfs(v); siz[u] += siz[v];        for(int now=min( siz[u],k+1 );now>=1;now--)        for(int w=min( siz[v],now-1 );w>=0;w--)            f[u][now] = max( f[u][now],f[u][now-w]+f[v][w] );    }}bool isok(double mid){
       for(int i=0;i<=n;i++)    for(int j=1;j<=k+1;j++)        f[i][j] = -inf;    for(int i=0;i<=n;i++)   v[i] = p[i]-mid*s[i];    dfs( 0 );    return f[0][k+1]>=0;}int main(){
       cin >> k >> n;    for(int i=1;i<=n;i++)    {
           scanf("%lf%lf%d",&s[i],&p[i],&r[i] );        add( r[i],i );    }    double l = 0, r = 1e4, ans = 0;    while( fabs(r-l)>eps )    {
           double mid = (l+r)/2.0;        if( isok(mid) ) l = mid+eps, ans = mid;        else    r = mid-eps;    }    printf("%.3lf",ans);}
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/115405825 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！