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