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

POJ 1947 Rebuilding Roads：樹形 DP 經典題目求隔離 P 個節點的最少刪邊數

編輯：關於C++

POJ 1947 Rebuilding Roads 完整解析

N 個節點（N ≤ 150）構成樹，求刪除最少邊使某連通塊恰好包含 P 個節點。經典樹形 DP，狀態定義於子樹內部。

狀態定義

dp[u][k]：以 u 為根的子樹中，保留恰好 k 個節點所需最少刪除邊數（僅計算子樹內部邊）。

狀態轉移

初始：dp[u][1] = 0（只保留根節點，無需刪邊），其餘 INF。

對每個子節點 v，合併其 DP 表：

for (int j = m; j >= 1; j--) {          // 當前子樹保留 j 個節點
    for (int k = 0; k < j; k++) {        // 從子節點 v 保留 k 個
        if (k == 0) {
            // 不保留 v 的任何節點 → 刪除邊 (u,v)
            dp[u][j] = min(dp[u][j], dp[u][j] + 1);
        } else {
            // 保留 v 的 k 個節點 → 合併，不刪邊 (u,v)
            dp[u][j] = min(dp[u][j], dp[u][j-k] + dp[v][k]);
        }
    }
}

最終答案

樹根 root 的 dp[root][P] 是以根為連通塊的答案。但連通塊可以在樹中任意位置，非根節點作為連通塊根時，還需額外刪除其連向父節點的邊（+1）。

ans = min(dp[root][P], min_{i≠root}(dp[i][P] + 1))

完整 AC 程式碼

#include <bits/stdc++.h>
using namespace std;

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

struct Edge { int to, next; } edges[MAXN * MAXN];
int head[MAXN], ecnt;
int n, P;
int fa[MAXN], dp[MAXN][MAXN];

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

void dfs(int u) {
    for (int i = 0; i <= P; i++) dp[u][i] = INF;
    dp[u][1] = 0;
    
    for (int e = head[u]; e != -1; e = edges[e].next) {
        int v = edges[e].to;
        dfs(v);
        
        // 合併子節點 v
        for (int j = P; j >= 1; j--) {
            for (int k = 0; k < j; k++) {
                if (k == 0) {
                    dp[u][j] = min(dp[u][j], dp[u][j] + 1);
                } else {
                    dp[u][j] = min(dp[u][j], dp[u][j-k] + dp[v][k]);
                }
            }
        }
    }
}

int main() {
    while (scanf("%d %d", &n, &P) == 2) {
        ecnt = 0;
        fill(head, head + n + 1, -1);
        fill(fa, fa + n + 1, -1);
        
        for (int i = 1; i < n; i++) {
            int u, v;
            scanf("%d %d", &u, &v);
            add_edge(u, v);
            fa[v] = u;
        }
        
        int root = 1;
        while (fa[root] != -1) root = fa[root];
        
        dfs(root);
        
        int ans = dp[root][P];
        for (int i = 1; i <= n; i++)
            if (i != root) ans = min(ans, dp[i][P] + 1);
        
        printf("%d\n", ans);
    }
    return 0;
}