Skip to content

「JSOI2016」最佳团体

题解约 1 千字
# 洛谷 # 动态规划 # LibreOJ # JSOI # 树形 DP # 2016
检测到 KaTeX 加载失败，可能会导致文中的数学公式无法正常渲染。

#题面

#题目描述

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

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

#输入格式

输入一行包含两个正整数 KK 和 NN。

接下来 NN 行，其中第 ii 行包含三个整数 Si,Pi,RiS_i, P_i, R_i，表示候选人 ii 的招募费用，战斗值和推荐人编号。

#输出格式

输出一行一个实数，表示最佳比值。答案保留三位小数。

#输入输出样例

样例输入 #1

1 2
1000 1 0
1 1000 1

样例输出 #1

0.001

#数据范围与提示

对于 100%100\% 的数据满足 1≤K≤N≤25001 \leq K \leq N \leq 2500，0<Si,Pi≤1040 < S_i, P_i \leq 10^4，0≤Ri<i0 \leq R_i < i。

#思路

分数规划 + 树形 DP。

二分之后问题就可以转化成以下形式了：

给定一棵根为 00 的树。每个点点权为 Pi−mid×SiP_i - \mathit{mid} \times S_i，选择一个点就必须选上它的所有祖先节点。求能否取 kk 个节点使得取出的点的点权之和大于零。

设 fu,if_{u, i} 表示以 uu 为根的子树选择 ii 个节点时的点权和的最大值，有两种情况：

  1. 不选 uu。此时这棵子树内的点一个也不能选取，fu,0=0f_{u, 0} = 0。
  2. 选 uu。枚举 uu 的每个子树。对于每个以 vv 为根的子树，枚举在 uu 内选取节点的总个数 ii 以及在子树 vv 内选取的个数 jj，有 fu,i=max⁡(fu,j,fu,i−j+fv,j)f_{u, i} = \max(f_{u, j}, f_{u, i - j} + f_{v, j})。

由于情况 11 的存在，i−ji - j 的值不能为 00，即不能选了 uu 的子树中的节点而不选 uu 本身。

在 void dfs(int) 中：C++
30
31
32
33
34
35
36
siz[u] += siz[v];

for (int i = std::min(siz[u], k + 1); i; i--) {
    for (int j = 0; j <= std::min(siz[v], i - 1); j++) {
        f[u][i] = std::max(f[u][i], f[u][i - j] + f[v][j]);
    }
}

#代码

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <iostream>
#include <algorithm>
#include <array>
#include <iomanip>
#include <limits>
#include <vector>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 2505;
const double eps = 1e-4;

int k, n;
std::array<int, N> siz;
std::array<double, N> d;
std::array<std::array<double, N>, N> f;
std::array<std::vector<int>, N> g;
std::array<std::pair<int, int>, N> a;

void dfs(int u) {
    f[u][0] = 0;
    f[u][1] = d[u];
    siz[u] = 1;

    for (int v : g[u]) {
        dfs(v);

        siz[u] += siz[v];

        for (int i = std::min(siz[u], k + 1); i; i--) {
            for (int j = 0; j <= std::min(siz[v], i - 1); j++) {
                f[u][i] = std::max(f[u][i], f[u][i - j] + f[v][j]);
            }
        }
    }
}

bool check(double mid) {
    for (int i = 1; i <= n; i++) {
        d[i] = static_cast<double>(a[i].second) - mid * a[i].first;
    }

    std::for_each(f.begin(), f.end(), [&](auto &x) {
        std::fill(x.begin(), x.end(), std::numeric_limits<int>::min());
    });

    dfs(0);

    return f[0][k + 1] >= 0;
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> k >> n;

    for (int i = 1, r; i <= n; i++) {
        cin >> a[i].first >> a[i].second >> r;

        g[r].emplace_back(i);
    }

    double l = 0,
           r = 10000;

    while (r - l > eps) {
        double mid = (l + r) / 2;

        if (check(mid)) l = mid;
        else r = mid;
    }

    cout << std::fixed << std::setprecision(3) << l << endl;

    return 0;
}