[JSOI 2016] 最佳团体

#include<bits/stdc++.h>using namespace std;#define MAXN 2510const double eps = 1e-4;const double inf = 1e9;int n , tot , k;int head[MAXN],a[MAXN],b[MAXN],size[MAXN],father[MAXN];double f[MAXN][MAXN];double value[MAXN],tmp[MAXN];struct edge{ ???????int to , nxt;} e[MAXN];template <typename T> inline void chkmax(T &x,T y) { x = max(x,y); }template <typename T> inline void chkmin(T &x,T y) { x = min(x,y); }template <typename T> inline void read(T &x){ ???T f = 1; x = 0; ???char c = getchar(); ???for (; !isdigit(c); c = getchar()) if (c == ‘-‘) f = -f; ???for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - ‘0‘; ???x *= f;}inline void dp(int u){ ???????size[u] = 1; ???????f[u][0] = 0; ???????f[u][1] = value[u]; ???????for (int i = head[u]; i; i = e[i].nxt) ???????{ ???????????????int v = e[i].to; ???????????????dp(v); ???????????????for (int j = 1; j <= size[u] + size[v]; j++) tmp[j] = -inf; ???????????????for (int j = 1; j <= size[u]; j++) ???????????????{ ???????????????????????for (int k = 0; k <= size[v]; k++) ???????????????????????{ ???????????????????????????????chkmax(tmp[j + k],f[u][j] + f[v][k]); ???????????????????????} ???????????????} ???????????????for (int j = 1; j <= size[u] + size[v]; j++) f[u][j] = tmp[j]; ???????????????size[u] += size[v]; ???????}}inline void addedge(int u,int v){ ???????tot++; ???????e[tot] = (edge){v,head[u]}; ???????head[u] = tot;}inline bool check(double mid){ ???????for (int i = 1; i <= n; i++) value[i] = (double)1.0 * b[i] - (double)1.0 * mid * a[i]; ???????for (int i = 0; i <= n; i++) ????????{ ???????????????for (int j = 0; j <= n + 1; j++) ???????????????{ ???????????????????????f[i][j] = -inf; ???????????????} ???????} ???????dp(0); ???????return f[0][k + 1] >= eps;}int main(){ ???????????????read(k); read(n); ???????for (int i = 1; i <= n; i++) ???????{ ???????????????read(a[i]); ????????????????read(b[i]); ????????????????read(father[i]); ???????????????addedge(father[i],i); ???????} ???????double l = 0 , r = 10000 , ans; ???????while (l + eps < r) ???????{ ???????????????double mid = (l + r) / 2.0; ???????????????if (check(mid)) ???????????????{ ???????????????????????l = mid; ???????????????????????ans = mid; ???????????????} else r = mid; ???????} ???????printf("%.3lf\n",ans); ???????????????return 0; ???}