[JSOI2016]最佳团体

 ?1 #include<cstdio> ?2 #include<iostream> ?3 #include<cmath> ?4 #include<algorithm> ?5 #include<cstring> ?6 #include<cstdlib> ?7 #include<cctype> ?8 #include<vector> ?9 #include<stack> 10 #include<queue> 11 using namespace std; 12 #define enter puts("") ?13 #define space putchar(‘ ‘) 14 #define Mem(a, x) memset(a, x, sizeof(a)) 15 #define rg register 16 typedef long long ll; 17 typedef double db; 18 const db INF = 1e12; 19 const db eps = 1e-5; 20 const int maxn = 2505; 21 inline ll read() 22 { 23 ????ll ans = 0; 24 ????char ch = getchar(), last = ‘ ‘; 25 ????while(!isdigit(ch)) {last = ch; ch = getchar();} 26 ????while(isdigit(ch)) {ans = (ans << 1) + (ans << 3) + ch - ‘0‘; ch = getchar();} 27 ????if(last == ‘-‘) ans = -ans; 28 ????return ans; 29 } 30 inline void write(ll x) 31 { 32 ????if(x < 0) x = -x, putchar(‘-‘); 33 ????if(x >= 10) write(x / 10); 34 ????putchar(x % 10 + ‘0‘); 35 } 36 ?37 int k, n, s[maxn], p[maxn]; 38 struct Edge 39 { 40 ????int nxt, to; 41 }e[maxn]; 42 int head[maxn], ecnt = -1; 43 void addEdge(int x, int y) 44 { 45 ????e[++ecnt] = (Edge){head[x], y}; 46 ????head[x] = ecnt; 47 } 48 ?49 int dfsx[maxn], pos[maxn], cnt = 0; 50 int siz[maxn]; 51 void dfs(int now) 52 { 53 ????dfsx[now] = ++cnt; pos[cnt] = now; 54 ????siz[now] = 1; 55 ????for(int i = head[now]; i != -1; i = e[i].nxt) 56 ????{ 57 ????????dfs(e[i].to); 58 ????????siz[now] += siz[e[i].to]; 59 ????} 60 } 61 db dp[maxn][maxn], w[maxn]; 62 db calc(int i, db x) 63 { 64 ????return (db)p[i] - (db)s[i] * x; 65 } 66 bool judge(db x) 67 { 68 ????for(int i = 1; i <= cnt; ++i) w[i] = calc(pos[i], x); 69 ????for(int i = 1; i <= cnt + 1; ++i) 70 ????????for(int j = 0; j <= k + 1; ++j) dp[i][j] = -INF; 71 ????dp[1][0] = 0; 72 ????for(int i = 1; i <= cnt; ++i) 73 ????????for(int j = 0; j <= min(i, k + 1); ++j) if(dp[i][j] > -INF) 74 ????????{ 75 ????????????dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + w[i]); 76 ????????????dp[i + siz[pos[i]]][j] = max(dp[i + siz[pos[i]]][j], dp[i][j]); 77 ????????} 78 ????db ans = -INF; 79 ????for(int i = 1; i <= cnt + 1; ++i) ans = max(ans, dp[i][k + 1]); 80 ????return ans > -eps; 81 } 82 ?83 int main() 84 { 85 ????Mem(head, -1); 86 ????k = read(); n = read(); 87 ????for(int i = 1; i <= n; ++i) 88 ????{ 89 ????????s[i] = read(); p[i] = read(); 90 ????????int x = read(); 91 ????????addEdge(x, i); 92 ????} 93 ????dfs(0); 94 ????db L = 0, R = 1e4; 95 ????while(R - L > eps) 96 ????{ 97 ????????db mid = (L + R) / 2; 98 ????????if(judge(mid)) L = mid; 99 ????????else R = mid;100 ????}101 ????printf("%.3lf\n", L);102 ????return 0;103 }