[JZOJ4512][JSOI2016]最佳团队

题目大意

一棵树，有 n+1 个节点，根编号为 0 。

每个非根节点都有两个权值si和 pi ，父亲 ri 。

要求选择 K+1 个节点，最大化

∑pi∑si

并且所选节点一定包括根，并且如果选择了节点 x(x≠0) 那么 x 的父亲ri一定要选。

1≤K≤n≤2500,0<si,pi≤104,0≤ri<i

题目分析

看见最大化的分式，显然要使用 01 分数规划。

二分答案转化为判定性问题，计算是否存在权值和小于零的选择方案。

由于这里有树形依赖关系，那我们需要用一个神奇的方法做树形 dp 。

注意到 x 的子树中任一节点能选择当且仅当x被选择。

所以我们可以按照 DFS 序列来 dp ，令 fi,j 表示待处理节点在 DFS 序中排名为 i ，已经选择了j个节点，令其节点编号为 p 。

∙如果选择了 p ，那么其子树就可以考虑，转移到fi+1,j+1

∙ 如果不选择 p ，那么就要跳过其子树，转移到fi+sizep,j

这个 dp 很巧妙，利用了树形依赖的性质。

时间复杂度 O(nKlog2(ns)) 。

代码实现

#include <iostream>
#include <climits>
#include <cfloat>
#include <cstdio>
#include <cctype>

using namespace std;

typedef double db;

int read()
{
    int x=,f=;
    char ch=getchar();
    while (!isdigit(ch)) f=(ch=='-')?-:f,ch=getchar();
    while (isdigit(ch)) x=x*+ch-'0',ch=getchar();
    return x*f;
}

const db INF=DBL_MAX/;
const db EPS=;
const int N=;
const int K=;

int fa[N],last[N],tov[N],next[N],s[N],p[N],size[N],id[N];
int n,k,tot,idx,sum;
db f[N][K],v[N];
db ans;

void insert(int x,int y)
{
    tov[++tot]=y,next[tot]=last[x],last[x]=tot;
}

void dfs(int x)
{
    size[id[++idx]=x]=;
    for (int i=last[x],y;i;i=next[i])
        dfs(y=tov[i]),size[x]+=size[y];
}

bool check(db now)
{
    for (int i=;i<=n+;i++)
    {
        v[i]=s[id[i]]*now-p[id[i]];
        for (int j=;j<=k;j++)
            f[i][j]=INF;
    }
    f[][]=;
    for (int i=;i<=n;i++)
    {
        for (int j=;j<=k&&j<=i-;j++)
        {
            if (f[i][j]<f[i+size[id[i]]][j]) f[i+size[id[i]]][j]=f[i][j];
            if (j<k&&f[i+][j+]>f[i][j]+v[i]) f[i+][j+]=f[i][j]+v[i];
        }
    }
    return f[n+][k]>;
}

double binary_search()
{
    db l=,r=sum,mid,ret;
    while (l+EPS<r)
    {
        mid=(l+r)/;
        if (check(mid)) r=mid;
        else ret=mid,l=mid;
    }
    return ret;
}

int main()
{
    freopen("team.in","r",stdin),freopen("team.out","w",stdout);
    k=read(),n=read();
    for (int i=;i<=n;i++)
    {
        s[i+]=read(),sum+=(p[i+]=read()),fa[i+]=read();
        insert(++fa[i+],i+);
    }
    n++;
    dfs();
    ans=binary_search();
    printf("%.3lf\n",ans);
    fclose(stdin),fclose(stdout);
    return ;
}