luogu P1642 规划

看到最后让求一个比值，应该得往01规划上去想。令x = ∑v[i] / ∑c[i],则x * ∑c[i] = ∑v[i], ∑(v[i] - x * c[i]) = 0.

于是可以二分x（注意是实数二分），每一个点得到新的权值v[i] - mid * c[i]，然后树上背包求最大值。如果最大值>0，说明x取消了，向[mid, R]二分；否则说明x取大了，向[L, mid]二分。

这个树上背包是比较经典的：求树上一个n - m的连通块，使块中的点的权值之和最大。

令dp[u][j]表示以u为根的子树中，有一个点数为 j 的联通块时的最大值。这个联通块一定是包含u的，否则就无法转移。然后就是相三层循环那样dp就行了（不过经过证明树上背包复杂度是O(n²)的）。

所以总复杂度O(n²logn)。

  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 int INF = 0x3f3f3f3f;
 19 const db eps = 1e-3;
 20 const int maxn = 105;
 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 * 10 + 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 n, m;
 38 struct Edge
 39 {
 40     int to, nxt;
 41 }e[maxn << 1];
 42 int head[maxn], ecnt = 0;
 43 void addEdge(int x, int y)
 44 {
 45     e[++ecnt].to = y;
 46     e[ecnt].nxt = head[x];
 47     head[x] = ecnt;
 48 }
 49 
 50 int v[maxn], c[maxn];
 51 db val[maxn], dp[maxn][maxn];
 52 
 53 int siz[maxn];
 54 void dfs(int now, int fa)
 55 {
 56     siz[now] = 1;
 57     dp[now][0] = 0;
 58     for(int i = head[now]; i; i = e[i].nxt)
 59     {
 60     if(e[i].to == fa) continue;
 61     dfs(e[i].to, now);
 62     siz[now] += siz[e[i].to];    
 63     for(int j = min(m, siz[now]); j >= 0; --j)
 64         for(int k = 0; k <= min(j, siz[e[i].to]); ++k)
 65         dp[now][j] = max(dp[now][j], dp[now][j - k] + dp[e[i].to][k]);
 66     }
 67     for(int i = min(m, siz[now]); i > 0; --i)
 68     dp[now][i] = dp[now][i - 1] + val[now];
 69 }
 70 
 71 bool judge(db x)
 72 {
 73     for(int i = 1; i <= n; ++i)    
 74     for(int j = 0; j <= m; ++j) dp[i][j] = -INF;
 75     for(int i = 1; i <= n; ++i) val[i] = (db)v[i] - x * (db)c[i];
 76     dfs(1, 0);
 77     for(int i = 1; i <= n; ++i)
 78     if(dp[i][m] > -eps) return 1;
 79     return 0;
 80 }
 81 
 82 int main()
 83 {
 84     n = read(); m = read();
 85     m = n - m;
 86     for(int i = 1; i <= n; ++i) v[i] = read();
 87     for(int i = 1; i <= n; ++i) c[i] = read();
 88     for(int i = 1; i < n; ++i)
 89     {
 90     int x = read(), y = read();
 91     addEdge(x, y); addEdge(y, x);
 92     }
 93     db L = 0, R = 1e6;
 94     while(R - L > eps)
 95     {
 96     db mid = (L + R) / 2.00;
 97     if(judge(mid)) L = mid;
 98     else R = mid;
 99     }
100     printf("%.1lf
", L);
101     return 0;
102 }

View Code