Skip to content

「JSOI2016」最佳团体

检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。

#题面

#题目描述

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

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

#输入格式

输入一行包含两个正整数 KKNN

接下来 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\% 的数据满足 1KN25001 \leq K \leq N \leq 25000<Si,Pi1040 < S_i, P_i \leq 10^40Ri<i0 \leq R_i < i

#思路

分数规划 + 树形 DP。

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

给定一棵根为 00 的树。每个点点权为 Pimid×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,ij+fv,j)f_{u, i} = \max(f_{u, j}, f_{u, i - j} + f_{v, j})

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

void dfs(int) 中:
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]);
}
}

#代码

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