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

HDU 4276 The Ghost Blows Light：樹形 DP + 主路徑偏移優化

編輯：C++ 入門

問題建模

樹上 N≤100 個節點，邊有權（時間）。節點 1 起點，N 終點。每節點有寶物值 A[i]。
限時 T≤500 分鐘內從 1 走到 N，可重複經過節點/邊，重複拾取寶物只算一次。
求最大寶物總值；若最短路徑 > T 輸出特定字串。

關鍵觀察：必經主路徑 + 側支探索

1→N 有唯一路徑（樹上任意兩點唯一路徑）。
設主路徑長度 sumT。若 sumT > T → 無解。
剩餘時間 T' = T - sumT 可用於「往返側支」收集寶物。
側支探索：從主路徑節點出發，走入子樹再原路返回，耗時 2×邊權之和。

兩階段 DP

階段 1：樹形 DP 計算每個主路徑節點的側支收益
dp[u][t] = 以 u 為根的子樹中（不含主路徑方向），耗時 t 往返能得的最大寶物。
背包合併：遍歷非主路徑兒子 v，耗時 cost = 2×edge(u,v)，值 dp[v][*]。
階段 2：主路徑上的分組背包
ans[t] = 前 i 個主路徑節點側支探索耗時 t 的最大收益。
最終答案 = sum(主路徑節點寶物) + max(ans[t]) (t ≤ T')。

完整代碼實現

#include 
#include 
#include 
#include 
#include 
using namespace std;

const int MAXN = 110, MAXT = 510;
int N, T;
int A[MAXN];
int dp[MAXN][MAXT]; // 階段1 DP
int ans[MAXT];      // 階段2 DP
bool on_path[MAXN]; // 是否在主路徑上
int path[MAXN], path_len;

struct Edge { int to, w, next; } e[MAXN*4];
int head[MAXN], ecnt;

void add_edge(int u, int v, int w) {
    e[ecnt] = {v, w, head[u]};
    head[u] = ecnt++;
}

void dfs_path(int u, int fa, int target) {
    if (u == target) { path[path_len++] = u; return; }
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to;
        if (v == fa) continue;
        dfs_path(v, u, target);
        if (path_len > 0) { path[path_len++] = u; return; }
    }
}

void tree_dp(int u, int fa) {
    dp[u][0] = A[u];
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to, w = e[i].w;
        if (v == fa || on_path[v]) continue; // 跳過主路徑方向
        tree_dp(v, u);
        // 背包合併：往返成本 2*w
        for (int t = T; t >= 0; t--) {
            if (dp[u][t] == 0 && t != 0) continue;
            for (int j = 0; j <= T - t - 2*w; j++) {
                if (dp[v][j])
                    dp[u][t + j + 2*w] = max(dp[u][t + j + 2*w], dp[u][t] + dp[v][j]);
            }
        }
    }
}

int main() {
    while (~scanf("%d%d", &N, &T)) {
        memset(head, -1, sizeof(head));
        ecnt = 0;
        for (int i = 0; i < N-1; i++) {
            int u, v, w; scanf("%d%d%d", &u, &v, &w);
            add_edge(u, v, w); add_edge(v, u, w);
        }
        for (int i = 1; i <= N; i++) scanf("%d", &A[i]);
        
        path_len = 0;
        dfs_path(1, 0, N);
        reverse(path, path + path_len); // 現在 path[0]=1, path[path_len-1]=N
        
        int sumT = 0;
        for (int i = 0; i < path_len; i++) on_path[path[i]] = true;
        // 計算主路徑總長
        for (int i = 0; i < path_len - 1; i++) {
            int u = path[i], v = path[i+1];
            for (int j = head[u]; ~j; j = e[j].next)
                if (e[j].to == v) { sumT += e[j].w; break; }
        }
        
        if (sumT > T) {
            puts("Human beings die in pursuit of wealth, and birds die in pursuit of food!");
            continue;
        }
        
        T -= sumT;
        // 階段1：每個主路徑節點做樹形DP
        for (int i = 0; i < path_len; i++) {
            memset(dp[path[i]], 0, sizeof(dp[path[i]]));
            tree_dp(path[i], 0);
        }
        
        // 階段2：主路徑分組背包
        memset(ans, 0, sizeof(ans));
        for (int i = 0; i < path_len; i++) {
            int u = path[i];
            for (int t = T; t >= 0; t--) {
                if (ans[t] == 0 && t != 0) continue;
                for (int j = 0; j <= T - t; j++) {
                    if (dp[u][j])
                        ans[t+j] = max(ans[t+j], ans[t] + dp[u][j]);
                }
            }
        }
        
        int maxv = 0;
        for (int i = 0; i <= T; i++) maxv = max(maxv, ans[i]);
        // 加上主路徑節點本身的寶物
        for (int i = 0; i < path_len; i++) maxv += A[path[i]];
        printf("%d\n", maxv);
    }
    return 0;
}