https://www.luogu.com.cn/problem/P4322

题解

网上怎么这么多假做法啊。。。一条链就卡掉了

假设0号节点是根 建出表示依赖关系的图 发现正好有条边且每个点的父亲都比它编号小所以正好是一棵树

那么原问题就是要在树上取一个包含根的性价比最高的连通块

看到”性价比”考虑使用01分数规划 假设表示第个人选不选 答案是 那么

挪一下

二分答案,如果上方左式可以大于0说明答案小了 否则答案大了

如何求出左式的最大值?

考虑dp,求出原树的dfs序,设表示考虑到dfs序为的点,共选了个点

是dfs序为的点的

可以选择这个点并且进入它的子树,即

可以不选这个点,这样它子树里的所有点都不能选了,所以直接跳到下一个在它子树外的点,假设它的dfs序是

这种按dfs序dp的方式常见于求包含根的连通块

先预处理一下每个点的dfs序和下一个它子树外的点的dfs序编号

一次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
#include <bits/stdc++.h>
#define N 2505
using namespace std;

template <typename T>
inline void read(T &num) {
T x = 0, ff = 1; char ch = getchar();
for (; ch > '9' || ch < '0'; ch = getchar()) if (ch == '-') ff = -1;
for (; ch <= '9' && ch >= '0'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ '0');
num = x * ff;
}

int m, n, a[N], b[N], dfn[N], ed[N], tme = -1;
int head[N], pre[N<<1], to[N<<1], sz;
double p[N], f[N][N], ans;

inline void addedge(int u, int v) {
pre[++sz] = head[u]; head[u] = sz; to[sz] = v;
pre[++sz] = head[v]; head[v] = sz; to[sz] = u;
}

void dfs(int x, int fa) {
dfn[x] = ++tme;
for (int i = head[x]; i; i = pre[i]) {
int y = to[i]; if (y == fa) continue; dfs(y, x);
}
ed[dfn[x]] = tme;
}

double check(double k) {
for (int i = 0; i <= n+1; i++) {
p[dfn[i]] = 1.0 * a[i] - k * b[i];
for (int j = 0; j <= m; j++) f[i][j] = -1e9;
}
f[0][0] = 0;
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
f[ed[i]+1][j] = max(f[ed[i]+1][j], f[i][j]);
if (j > 0) f[i+1][j] = max(f[i+1][j], f[i][j-1] + p[i]);
}
}
return f[n+1][m];
}

int main() {
read(m); read(n); ++m;
for(int i = 1, x; i <= n; i++) {
read(b[i]); read(a[i]); read(x);
addedge(x, i);
}
dfs(0, 0);
double l = 0, r = 1e4, mid = 0;
while (r - l > 1e-5) {
mid = (l + r) / 2;
if (check(mid) > 0) {
l = mid + 1e-7;
} else r = mid - 1e-7;
}
printf("%.3lf\n", l);
return 0;
}

评论