UVa 2038 Strategic Game：樹上最小頂點覆蓋 = 最大匹配 / 2

題目大意

給一棵樹（n ≤ 1500 節點），邊以鄰接表形式輸入（每行：節點:(度數) 相鄰節點...）。選最少節點放置士兵，使得**每條邊至少一個端點有士兵**。輸出最少士兵數。多測試案例。

核心定理：樹上最小頂點覆蓋 = 最大匹配數

• 樹是二分圖（無奇環）。
• Kőnig 定理：二分圖中，最小頂點覆蓋數 = 最大匹配數。
• 最大匹配中每條邊貢獻 2 個端點，故最小頂點覆蓋 = 最大匹配邊數 = 匹配邊數（因每條匹配邊對應一個覆蓋頂點）。實際上：最小頂點覆蓋 = 最大匹配邊數。代碼中用匈牙利算法求最大匹配，答案 = 匹配數 / 2（因無向圖每條邊存兩次，匹配時每條邊被雙向匹配一次）。

算法：匈牙利算法 (DFS 版) 求最大匹配

• 建圖：無向邊雙向存儲。
• 從每個未匹配左部節點發起 DFS 增廣路搜索。
• 時間 O(V×E) = 1500 × 3000 = 4.5×10⁶，極快。

關鍵代碼

#include 
#include 
#include 
using namespace std;
const int MAXN = 1510;
vector g[MAXN];
int match[MAXN], vis[MAXN], visToken;
int n;

bool dfs(int u) {
    if (vis[u] == visToken) return false;
    vis[u] = visToken;
    for (int v : g[u]) {
        if (match[v] == -1 || dfs(match[v])) {
            match[u] = v;
            match[v] = u;
            return true;
        }
    }
    return false;
}

int hungarian() {
    memset(match, -1, sizeof(match));
    int res = 0;
    for (int u = 0; u < n; ++u) {
        if (match[u] == -1) {
            ++visToken;
            if (dfs(u)) ++res;
        }
    }
    return res; // 匹配邊數（每條邊雙向算一次，實際匹配邊數 = res/2）
}

int main() {
    while (scanf("%d", &n) == 1 && n) {
        for (int i = 0; i < n; ++i) g[i].clear();
        for (int i = 0; i < n; ++i) {
            int u, deg; scanf("%d:(%d)", &u, °);
            while (deg--) {
                int v; scanf("%d", &v);
                g[u].push_back(v);
                g[v].push_back(u);
            }
        }
        int maxMatch = hungarian();
        printf("%d\n", maxMatch / 2);
    }
    return 0;
}

替代做法：樹形 DP

狀態：dp[u][0/1] = 以 u 為根的子樹，u 不放/放士兵的最小覆蓋數。
轉移：
dp[u][1] = 1 + sum(min(dp[v][0], dp[v][1]))
dp[u][0] = sum(dp[v][1])（u 不放，所有子必須放）
答案 = min(dp[root][0], dp[root][1])。
此法更直觀、不需建二分圖、O(n) 時間。

總結

UVa 2038 是「樹上最小頂點覆蓋」的標準題。既可用「最大匹配/2」（匈牙利），也可用「樹形 DP」。樹形 DP 代碼更短、常數更小、邏輯更直接，推薦作為首選模板。