洛谷P4322 [JSOI2016]最佳团体 题解

题目链接：P4322 [JSOI2016]最佳团体

题意：

JSOI 信息学代表队一共有 $N$ 名候选人，这些候选人从 $1$ 到 $N$ 编号。方便起见，JYY 的编号是 $0$ 号。每个候选人都由一位编号比他小的候选人$R_i$ 推荐。如果 $R_i = 0$，则说明这个候选人是 JYY 自己看上的。

为了保证团队的和谐，JYY 需要保证，如果招募了候选人 $i$，那么候选人 $R_i$ 也一定需要在团队中。当然了，JYY 自己总是在团队里的。每一个候选人都有一个战斗值 $P_i$ ，也有一个招募费用 $S_i$ 。JYY 希望招募 $K$ 个候选人（JYY 自己不算），组成一个性价比最高的团队。也就是，这 $K$ 个被 JYY 选择的候选人的总战斗值与总招募费用的比值最大。

对于100%的数据满足$1≤K≤N≤2500$,$0<S_i,P_i≤10^4$ ,
$0$ $≤$ $R_i$ $<$ $i$

下面的讲述用 $m$ 代替 $K$ ，$n$ 代替 $N$ 。

这个分数怎么dp呢？

其实这题就是01分数规划+树上背包的简单有趣题

设某次选择的答案为

$$\sum P_i \times \dfrac{1}{\sum S_i}$$

设

$$\sum P_i \times \dfrac{1}{\sum S_i} \ge x$$

移项可得

$$\sum(P_i-xS_i) \ge 0$$

二分一个 $x$ ，注意 $x$ 为实数且 $x \in [1,10^4]$

则dp的价值就变成了价值为 $C_i = P_i - x S_i$ 的人 $i$

设 $dp[u][j]$ 表示 $u$ 子树选恰好 $j$ 个人时能获得的最大价值

则有转移方程

$$dp[u][j+k]=\max_{1 \le j \le \min(m,\text{sz}[u]),0 \le k \le \min(m,\text{sz}[v])}(dp[u][j+k],\text{tmp}[j] + dp[v][k])$$

其中 $\text{tmp}[j]$ 为上一轮的 $dp[u][j]$

因为选了儿子一定要选父亲，因此转移时 $j$ 要从 $1$ 开始

然后我们直接把 $0$ 当做一个没有价值的人，然后把m=m+1

每次二分时判断 $dp[u][m]\ge0$ 是否成立，成立就l=mid

然后每次dp的时候sz都要重新算，否则复杂度是假的。

细节比较多，详见代码。

时间复杂度 $O(\log_2 10^4 \times nm)$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(3e3+15)
const double eps=1e-13;
int n,m,sz[N],s[N],p[N];
vector<int> vec[N];
double dp[N][N],tmp[N],c[N];
void dfs(int u)
{
    sz[u]=1;
    dp[u][0]=0;dp[u][1]=c[u];
    for(int v : vec[u])
    {
        dfs(v);
        for(int j=1; j<=min(sz[u],m); j++)
            tmp[j]=dp[u][j];
        for(int j=1; j<=min(sz[u],m); j++)
            for(int k=0; k<=min(sz[v],m)&&j+k<=m; k++)
                dp[u][j+k]=fmax(dp[u][j+k],tmp[j]+dp[v][k]);
        sz[u]+=sz[v];
    }
}
bool ck(double x)
{
    for(int i=0; i<=n; i++)
    {
        c[i]=p[i]-x*s[i];
        for(int j=1; j<=m; j++)
            dp[i][j]=-1e100;
    }
    dfs(0);return dp[0][m]>=-eps;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> m >> n;++m;
    for(int i=1,fa; i<=n; i++)
    {
        cin >> s[i] >> p[i] >> fa;
        vec[fa].push_back(i);
    }
    double l=0,r=1e4;
    while(fabs(r-l)>1e-7)
    {
        double mid=(l+r)/2;
        if(ck(mid))l=mid;
        else r=mid;
    }
    cout << fixed << setprecision(3);
    cout << l << '\n';
    return 0;
}