HDOJ 4276 The Ghost Blows Light：SPFA + 樹形 DP 最大寶物收集

問題描述

墓室為一棵樹（N ≤ 100），節點 1 為入口，節點 N 為出口。每條邊有通行時間，每個房間有寶物價值。限時 T 分鐘內從 1 走到 N，並可繞路收集寶物（繞路需往返，雙倍邊權），求最大收集寶物數。若無法在 T 內到達出口，輸出特定字串。

解題思路

1. SPFA 求最短路：從 1 到 N 的最短路徑時間 dist[N]。若 dist[N] > T，無解。
2. 剩餘時間：T' = T - dist[N]。最短路上的邊權設為 0（來回不消耗額外時間），其餘邊權乘 2（往返雙倍）。
3. 樹形 DP (背包)：以 1 為根 DFS。dp[u][t] 表示在子樹 u 中花費 t 時間可得最大寶物。合併子樹時雙重循環背包轉移：dp[u][j] = max(dp[u][j], dp[u][j-k-cost] + dp[v][k])，其中 cost 為邊權（0 或 2*w）。
4. 答案為 dp[1][T']。

關鍵細節

• SPFA 記錄前驅邊，將最短路邊權歸零。
• DP 初始化：dp[u][*] = a[u]（本節點寶物）。
• 時間限制 T ≤ 500，N ≤ 100，DP 狀態數 100×500 完全可行。

複雜度

• SPFA：O(N+E) 期望線性。
• 樹形 DP：O(N × T^2) 最壞，實際隨邊權分布較小。

參考程式碼 (C++)

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
struct Edge { int to, w, nxt; } e[500];
int head[110], ecnt, n, T;
int a[110], dis[110], pre[110], pre_e[110];
int dp[110][510];

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

void spfa(int s) {
    fill(dis+1, dis+n+1, INF);
    fill(pre+1, pre+n+1, -1);
    queue q; q.push(s); dis[s]=0;
    vector inq(n+1); inq[s]=1;
    while (!q.empty()) {
        int u = q.front(); q.pop(); inq[u]=0;
        for (int i=head[u]; ~i; i=e[i].nxt) {
            int v = e[i].to, w = e[i].w;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                pre[v] = u; pre_e[v] = i;
                if (!inq[v]) { inq[v]=1; q.push(v); }
            }
        }
    }
    // 最短路邊權歸零
    for (int u=n; u!=1; u=pre[u]) {
        e[pre_e[u]].w = 0;
        e[pre_e[u]^1].w = 0;
    }
}

void dfs(int u, int fa) {
    for (int i=0;i<=T;i++) dp[u][i] = a[u];
    for (int i=head[u]; ~i; i=e[i].nxt) {
        int v = e[i].to; if (v==fa) continue;
        dfs(v, u);
        int cost = e[i].w * 2;
        for (int j=T; j>=cost; --j)
            for (int k=0; k+cost<=j; ++k)
                dp[u][j] = max(dp[u][j], dp[u][j-k-cost] + dp[v][k]);
    }
}

int main() {
    while (cin >> n >> T) {
        memset(head, -1, sizeof(head)); ecnt=0;
        for (int i=0;i>u>>v>>w;
            add_edge(u,v,w); add_edge(v,u,w);
        }
        for (int i=1;i<=n;i++) cin>>a[i];
        spfa(1);
        if (dis[n] > T) {
            cout << "Human beings die in pursuit of wealth, and birds die in pursuit of food!\n";
            continue;
        }
        T -= dis[n];
        memset(dp, 0, sizeof(dp));
        dfs(1, -1);
        cout << dp[1][T] << '\n';
    }
    return 0;
}