洛谷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;
}