您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

POJ 1155 TELE - 樹形 DP + 分組背包詳解

編輯：關於C++

題目大意

給定一棵以 1 為根的樹，節點 1 是電視台，葉子節點是潛在用戶（共 M 個），中間節點是轉播站。每條邊有傳輸成本。每個用戶願意支付一定費用觀看比賽。電視台可選擇服務哪些用戶，目標是 在不虧損（總收入 ≥ 總成本）的前提下，最大化服務用戶數。N ≤ 3000。

分析與狀態定義

這是一棵樹上的決策問題。對每個節點 u，考慮其子樹內選擇 k 個用戶所能獲得的 最大淨收益（收入 - 成本）。定義：

dp[u][k]：在以 u 為根的子樹中，選擇 k 個用戶，扣除子樹內所有邊的傳輸成本後的最大淨收益。若不可行則為 -∞。
sz[u]：u 的子樹中用戶總數（葉子節點為 1，內部節點為子節點之和）。

狀態轉移（分組背包）

對於內部節點 u，其子節點 v 之間互斥（屬於不同分支），屬於典型的「分組背包」：從每個子節點的子樹中選若干用戶，合併到 u。轉移方程：

dp[u][j] = max( dp[u][j], dp[u][j - t] + dp[v][t] - cost(u,v) )
// j 從 sz[u] 遞減到 1，t 從 1 到 sz[v]

其中 cost(u,v) 是邊 (u,v) 的傳輸成本。注意：每條邊的成本只在「選擇了該子樹至少一個用戶」時扣除一次，因此在合併子節點 v 時統一扣除 cost(u,v)。

葉子節點初始化

用戶節點 i (i > N-M)：dp[i][0] = 0（不選），dp[i][1] = pay[i]（選該用戶，收入為其支付意願）。

最終答案

在根節點 1 中，從大到小掃描 dp[1][k]，第一個 ≥ 0 的 k 即為最大可服務用戶數。

關鍵代碼 (C++)

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 3005;
const int INF = 0x3f3f3f3f;

struct Edge { int to, cost; };
vector<Edge> G[MAXN];
int pay[MAXN], sz[MAXN];
int dp[MAXN][MAXN];
int N, M;

void dfs(int u, int fa) {
    if (G[u].empty()) { // 葉子（用戶）
        sz[u] = 1;
        dp[u][0] = 0;
        dp[u][1] = pay[u];
        return;
    }
    dp[u][0] = 0;
    for (auto &e : G[u]) {
        int v = e.to, c = e.cost;
        if (v == fa) continue;
        dfs(v, u);
        // 分組背包合併
        for (int j = sz[u]; j >= 1; --j) {
            for (int t = 1; t <= sz[v]; ++t) {
                if (dp[u][j - t] > -INF && dp[v][t] > -INF) {
                    dp[u][j] = max(dp[u][j], dp[u][j - t] + dp[v][t] - c);
                }
            }
        }
        sz[u] += sz[v];
    }
}

int main() {
    while (cin >> N >> M) {
        for (int i = 1; i <= N; ++i) {
            G[i].clear();
            fill(dp[i], dp[i] + N + 1, -INF);
        }
        for (int i = 1; i <= N - M; ++i) {
            int k; cin >> k;
            while (k--) {
                int a, c; cin >> a >> c;
                G[i].push_back({a, c});
                G[a].push_back({i, c});
            }
        }
        for (int i = N - M + 1; i <= N; ++i) cin >> pay[i];
        dfs(1, 0);
        for (int k = M; k >= 0; --k) {
            if (dp[1][k] >= 0) { cout << k << '\n'; break; }
        }
    }
    return 0;
}