$ \color{#0066ff}{ 題目描述 }$

某地方有N個工廠，有N-1條路連接它們，且它們兩兩都可達。每個工廠都有一個產量值和一個污染值?，F在工廠要進行規劃，拆除其中的M個工廠，使得剩下的工廠依然連成一片且 總產量/總污染 的值最大。

\(\color{#0066ff}{輸入格式}\)

第一行N M(1<N<100,1<=M<N),表示工廠個數和要拆除的個數。

第二行N個正整數，表示每個工廠的產值[1..10000]

第三行N個正整數，表示每個工廠的污染值[1..10000]

接著N-1行，每行兩個正整數a b(1<=a,b<=N)表示a,b之間相連。

\(\color{#0066ff}{輸出格式}\)

總產量/總污染 的最大值，保留一位小數。

\(\color{#0066ff}{輸入樣例}\)

3 2 2 3 4 1 1 1 1 2 2 3

\(\color{#0066ff}{輸出樣例}\)

4.0

\(\color{#0066ff}{數據范圍與提示}\)

none

\(\color{#0066ff}{題解}\)

顯然是01分數規劃問題，那么二分答案

現在的問題是找一個大小為m的聯通塊

經典樹形DP，\(f[i][j]\)為以i為根子樹選j個點的最大值（i必選）

跑樹形背包即可，注意i必選的限制，所以要對所有點取max

#include<bits/stdc++.h> #define LL long long LL read() {char ch; LL x = 0, f = 1;while(!isdigit(ch = getchar()))(ch == '-') && (f = -f);for(x = ch ^ 48; isdigit(ch = getchar()); x = (x << 1) + (x << 3) + (ch ^ 48));return x * f; } template<class T> bool chkmax(T &a, const T &b) { return a < b? a = b, 1 : 0; } template<class T> bool chkmin(T &a, const T &b) { return b < a? a = b, 1 : 0; } const int inf = 0x7fffffff; const int maxn = 555; const double eps = 1e-6; int n, m, a[maxn], b[maxn], siz[maxn]; double f[maxn][maxn], val[maxn], mx; std::vector<int> G[maxn]; void dfs(int x, int fa) {siz[x] = 1;f[x][0] = 0, f[x][1] = val[x];for(auto to : G[x]) {if(to == fa) continue;dfs(to, x);siz[x] += siz[to];for(int i = std::min(m, siz[x]); i >= 1; i--)for(int j = 0; j < i; j++)chkmax(f[x][i], f[x][i - j] + f[to][j]);}chkmax(mx, f[x][m]); } bool ok(double mid) {for(int i = 1; i <= n; i++)for(int j = 0; j <= m; j++) f[i][j] = -inf;for(int i = 1; i <= n; i++) val[i] = (double)(a[i] - mid * b[i]);mx = -1e18;dfs(1, 0);return mx >= 0; }int main() {n = read(), m = n - read();for(int i = 1; i <= n; i++) a[i] = read();for(int i = 1; i <= n; i++) b[i] = read();int x, y;for(int i = 1; i < n; i++) {x = read(), y = read();G[x].push_back(y);G[y].push_back(x);}double l = 0, r = 105050;while(r - l > eps) {double mid = (l + r) / 2.0;if(ok(mid)) l = mid;else r = mid;}printf("%.1f\n", l);return 0; }

轉載于:https://www.cnblogs.com/olinr/p/10652961.html

總結

以上是生活随笔為你收集整理的P1642 规划 01分数规划+树形DP的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。