UVA 1292 - 樹的最小頂點覆蓋：樹形 DP 經典解法

問題描述

給定一棵無根樹，選擇最少數量的節點，使得每條邊至少有一個端點被選中（即「覆蓋」所有邊）。求最小覆蓋節點數。

解題思路：樹形動態規劃

任選一節點為根（如 0），將無根樹轉為有根樹。對每個節點 i 定義兩種狀態：

• dp[i][0]：不選節點 i 時，覆蓋以 i 為根的子樹所需最少節點數
• dp[i][1]：選節點 i 時，覆蓋以 i 為根的子樹所需最少節點數

狀態轉移方程

設 u 為 i 的孩子：

• 若 不選 i，則每條邊 (i,u) 必須由 u 覆蓋 → 所有孩子 必須被選
  dp[i][0] = Σ dp[u][1]
• 若 選 i，邊 (i,u) 已被覆蓋，孩子 u 可選可不選 → 取較小值
  dp[i][1] = Σ min(dp[u][0], dp[u][1]) + 1 （+1 計算節點 i 本身）

算法流程

1. 建立鄰接表存儲樹
2. DFS 遞歸計算 dp 值（後序遍歷）
3. 答案為 min(dp[root][0], dp[root][1])

C++ 實現

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 1550;
vector adj[MAXN];
int dp[MAXN][2];
bool vis[MAXN];
int n;

void dfs(int u) {
    vis[u] = true;
    dp[u][0] = 0;
    dp[u][1] = 1; // 選自己
    for (int v : adj[u]) {
        if (vis[v]) continue;
        dfs(v);
        dp[u][0] += dp[v][1];
        dp[u][1] += min(dp[v][0], dp[v][1]);
    }
}

int main() {
    while (scanf("%d", &n) != EOF) {
        for (int i = 0; i <= n; ++i) {
            adj[i].clear();
            vis[i] = false;
            dp[i][0] = dp[i][1] = 0;
        }
        for (int i = 0; i < n; ++i) {
            int x, num, y;
            scanf("%d:(%d)", &x, &num);
            for (int j = 0; j < num; ++j) {
                scanf("%d", &y);
                adj[x].push_back(y);
                adj[y].push_back(x);
            }
        }
        dfs(0);
        printf("%d\n", min(dp[0][0], dp[0][1]));
    }
    return 0;
}

複雜度

• 時間：O(N)，每條邊訪問一次
• 空間：O(N)