题目链接(Luogu)
题目链接(LibreOJ)
题目概括重金征集中~
0/1 分数规划的基本模型：给定整数 $a_1,a_2,…,a_n$ 以及 $b_1,b_2,…,b_n$，求一组解 $x_i$（$x_i$ 的取值为 0 或 1），使下式最大化：
$$
\frac{\Sigma a_ix_i}{\Sigma b_ix_i}
$$
在本题中，${a_n}$ 对应着战斗值， ${b_n}$ 对应着招募费用。题目要求从中选出若干名选手（即将相应的 $x_i$ 赋为 1），使得上式最大化。
值得注意的是，在本题中 $x_i$ 的取值同样有限制：如果 $x_i=1$，则一定有 $x_{R[i]}=1$ 或$R[i]=0$。
接下来考虑上式的计算。我么们不妨任意猜测一个值 $mid$ ，如果 $\frac{\Sigma a_i*x_i}{\Sigma b_i*x_i} \ge mid$ ，即 $mid$ 比我们要求的最大值要小，则可以推出 $\Sigma (a_i-mid*b_i)*x_i\ge 0$。因此，我们只需判定 $\Sigma (a_i-mid*b_i)*x_i$ 是否大于等于 0，即可进一步缩小 $mid$ 的范围。
综上所述，我们可以二分答案（实数）。当二分的值为 $mid$ 时，计算 $\Sigma (a_i-mid*b_i)*x_i$ 的最大值，检查最大值是否非负。若非负，则令 $l=mid$；否则令 $r=mid$。当二分停止时，就得到了 0/1 分数规划问题的解。
本题的另一关键点在于计算 $\Sigma (a_i-mid*b_i)*x_i$ 的最大值。本题可以采用背包类树形 DP 实现，具体内容不再赘述。
代码如下：
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
| #include <bits/stdc++.h>
using namespace std;
const float eps = 1e-4;
struct Edge {
int v, nxt;
}edge[2505];
int cnt, head[2505];
inline void AddEdge(int u, int v) {
edge[++cnt].v = v;
edge[cnt].nxt = head[u];
head[u] = cnt;
}
int K, N;
int a[2505], b[2505];
float f[2505][2505];
int size[2505];
float delta;
inline void dfs(int u) {
size[u] = 1;
for (int i = head[u]; i; i = edge[i].nxt) {
dfs(edge[i].v);
size[u] += size[edge[i].v];
}
}
inline void dp(int u) {
float w = 1.0 * a[u] - 1.0 * delta * b[u];
for (int i = 1; i <= K; ++i)
f[u][i] = -1e9;
for (int i = head[u]; i; i = edge[i].nxt) {
int v = edge[i].v;
dp(v);
for (int i = min(K, size[u]); i >= 1; --i)
for (int j = 0; j <= min(size[v], i); ++j)
f[u][i] = max(f[u][i], f[u][i - j] + f[v][j]);
}
if (u != 0) {
for (int i = min(K, size[u]); i >= 1; --i)
f[u][i] = f[u][i - 1] + w;
f[u][1] = w;
}
}
int main() {
scanf("%d%d", &K, &N);
for (register int i = 1; i <= N; ++i) {
int r;
scanf("%d%d%d", &b[i], &a[i], &r);
AddEdge(r, i);
}
dfs(0);
float l = 0, r = 10000;
while (r - l > eps) {
float mid = (l + r) / 2;
delta = mid;
dp(0);
if (f[0][K] < 0) r = mid;
else l = mid;
}
printf("%.3f", l);
return 0;
}
|