🔗 UVA-1292 Strategic game

tags: `動態規劃(DP)` `樹(Tree)` `樹形DP` `DFS` `最小支配集(Minimum Dominating Set)`

範例程式碼已於UVA、瘋狂程設(CPE)、ZeroJudge 上皆測試通過。

題意

給定一個具有 $n$ 個節點的樹(Tree) ，可以在每個節點上放置士兵，也可以不放置，每個節點上的士兵可以觀察到與該節點相連的所有邊。

求要觀察到所有的邊，最少需要放置多少士兵。

思路：樹形DP + DFS

這是一個典型的最小支配集(Minimum Dominating Set) 問題，在樹上放置最少數量的士兵以覆蓋所有的邊。

由於每個節點都有放置或不放置兩種選擇，因此可以使用樹形DP(Tree DP) 來解決。

定義 $dp[u][0]$ 表示當前節點 $u$ 不放置士兵的最小花費， $dp[u][1]$ 表示當前節點 $u$ 放置士兵的最小花費，則有：

$dp[u][0] = \sum_{v \in \text{children}(u)} dp[v][1]$
當前節點不放置士兵，則子節點必須放置士兵，才能監視到與子節點相連的邊
$dp[u][1] = 1 + \sum_{v \in \text{children}(u)} \min(dp[v][0], dp[v][1])$
當前節點放置士兵，則子節點可以放置或不放置士兵

由於樹上任何節點都可以作為根節點，因此可以從任意節點開始進行樹形DP，最後取該節點的 $dp[root][0]$ 和 $dp[root][1]$ 的最小值即可。

這裡使用了 Top-Down 的 DFS 來實現樹形DP，當然也可以使用 Bottom-Up 的方式，但必須從葉節點開始遍歷。前者甚至可以不用建立額外的陣列，直接在 DFS 遞迴中進行計算，如範例的 Python 程式碼。

複雜度分析

時間複雜度： $\mathcal{O}(n)$ ，所有節點只需遍歷一次。
空間複雜度： $\mathcal{O}(n)$ ，遞迴深度為 $O(n)$ ，若建立 $dp$ 陣列的話也為 $O(n)$ 。

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
def print(val=""):
    sys.stdout.write(str(val) + "\n")

while True:
    try:
        n = int(input())
    except:
        break

    g = [[] for _ in range(n)]
    for _ in range(n):
        line = input()
        co, lp, rp = line.index(':'), line.index('('), line.index(')')
        u, d = int(line[:co]), int(line[lp+1:rp])
        nodes = list(map(int, line[rp+2:].split()))
        for v in nodes:
            g[u].append(v)
            g[v].append(u)

    def dfs(u, fa):
        f0, f1 = 0, 1 # 當前節點 不放置/放置 的最小花費
        for v in g[u]:
            if v == fa:
                continue
            r0, r1 = dfs(v, u)
            f0 += r1 # 若不放置，下一層必須放置
            f1 += min(r0, r1) # 若放置，下一層可放置或不放置
        return f0, f1
    print(min(dfs(0, -1))) # 可以以任意點為根

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'

vector<vector<int>> g;
vector<vector<int>> dp;

void dfs(int u, int fa) {
    dp[u][0] = 0;
    dp[u][1] = 1;
    for (int v : g[u]) {
        if (v == fa) {
            continue;
        }
        dfs(v, u);
        dp[u][0] += dp[v][1];
        dp[u][1] += min(dp[v][0], dp[v][1]);
    }
}

int main() {
    // 混用 cin/cout 和 scanf/printf 就不能取消同步
    // ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int n, u, d, v;
    while (cin >> n && n) {
        g.clear();
        g.resize(n);
        dp.clear();
        dp.resize(n, vector<int>(2, 0));
        for (int i=0; i<n; i++) {
            scanf("%d:(%d)", &u, &d);
            int v;
            for (int j=0; j<d; j++) {
                cin >> v;
                g[u].push_back(v);
                g[v].push_back(u);
            }
        }
        dfs(0, -1);
        cout << min(dp[0][0], dp[0][1]) << endl;
    }
    return 0;
}