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