01分数规划

显然可以二分最大比值x，来验证是否可行

记当前比值为x，总战斗值为P与总招募费用为S

则 P - x*S >= 0

设 wi = pi - x*si

即 w1 + w2 + ... + wk >= 0

就转化为选k个节点，它们的w值非负，树上简单地dp一下就可求得

 1 #include <bits/stdc++.h> 2 using namespace std; 3  4 const int N = 2505; 5  6 double l, r = 1e4, mid, f[N][N], w[N], ans, eps = 1e-5; 7 int siz[N], fa[N], p[N], s[N]; 8 int n, m, first[N], cnt; 9 struct Edge {10 int to, next;11 } e[N];12 13 void dfs(int u) {14 siz[u] = 1;15 f[u][1] = w[u];16 for (int i = first[u]; i != -1; i = e[i].next) {17 int v = e[i].to;18  dfs(v);19 siz[u] += siz[v];20 for (int j = min(siz[u], m); j >= 2; j--)21 for (int k = 1; k <= min(j - 1, siz[v]); k++) f[u][j] = max(f[u][j], f[v][k] + f[u][j - k]);22  }23 }24 25 bool check(double x) {26 memset(f, -0x3f, sizeof(f));27 for (int i = 0; i <= n; i++) f[i][0] = 0;28 for (int i = 1; i <= n; i++) w[i] = (double)p[i] - s[i] * x;29 dfs(0);30 return f[0][m] >= 0;31 }32 33 void add(int u, int v) {34 e[cnt].to = v;35 e[cnt].next = first[u];36 first[u] = cnt++;37 }38 39 int main() {40 memset(first, -1, sizeof(first));41 cin >> m >> n;42 m++;43 for (int i = 1; i <= n; i++) {44 scanf("%d%d%d", &s[i], &p[i], &fa[i]);45  add(fa[i], i);46  }47 while (r - l > eps) {48 mid = (r + l) / 2;49 dfs(0);50 if (check(mid))51 l = mid + eps, ans = mid;52 else53 r = mid - eps;54  }55 printf("%.3f\n", ans);56 }