UVA 10859 Placing Lampposts - 樹形 DP 最小點覆蓋變體

問題描述

給定樹（圖無環），在節點放路燈。每條邊至少一端點有路燈。目標：最小化路燈數；在最小路燈數下，最大化被兩盞路燈照亮的邊數；再最大化只被一盞路燈照亮的邊數。輸出：路燈數、被兩盞照亮的邊數、被一盞照亮的邊數。

樹形 DP 狀態定義

對每個節點 u，定義：

• dp[u][0]：u 不放路燈時，子樹內的最優解（路燈數 * M + 邊數編碼）。
• dp[u][1]：u 放路燈時的最優解。

其中 M 為足夠大的常數（如 2005），將多目標優化轉化為單一值比較：優先最小化路燈數，次優最大化雙覆蓋邊，再次最大化單覆蓋邊。

狀態轉移

• u 放燈：dp[u][1] = 1*M + Σ min(dp[v][0]+1, dp[v][1])。邊 (u,v) 若 v 也放燈則雙覆蓋（+1），否則單覆蓋（+0）。
• u 不放燈：dp[u][0] = 0*M + Σ (dp[v][1] + 1)。強制子節點 v 必須放燈，邊 (u,v) 單覆蓋（+1）。

代碼實現（Java）

import java.util.*;

public class Main {
    static final int N = 1005, M = 2005;
    static ArrayList[] G = new ArrayList[N];
    static int[][] dp = new int[N][2];
    static boolean[] vis = new boolean[N];
    static int n, m;

    static int min(int a, int b) { return a < b ? a : b; }

    static int dfs(int u) {
        vis[u] = true;
        dp[u][0] = 0;
        dp[u][1] = M; // 放燈基礎代價 1*M
        for (int v : G[u]) {
            if (vis[v]) continue;
            dfs(v);
            dp[u][1] += min(dp[v][0] + 1, dp[v][1]); // 邊覆蓋代價在子節點處理
            dp[u][0] += dp[v][1] + 1; // 強制子節點放燈，邊單覆蓋
        }
        return min(dp[u][0], dp[u][1]);
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        while (T-- > 0) {
            n = in.nextInt(); m = in.nextInt();
            for (int i = 0; i < n; i++) { G[i] = new ArrayList<>(); vis[i] = false; }
            for (int i = 0; i < m; i++) {
                int u = in.nextInt(), v = in.nextInt();
                G[u].add(v); G[v].add(u);
            }
            int ans = 0;
            for (int i = 0; i < n; i++) if (!vis[i]) ans += dfs(i);
            int lamps = ans / M;
            int doubleCover = m - ans % M;
            int singleCover = ans % M;
            System.out.printf("%d %d %d\n", lamps, doubleCover, singleCover);
        }
    }
}

關鍵技巧

• 將多目標優化合併為單一整數權值，利用大常數 M 分離優先級。
• 樹可能為森林，需對每個連通分量跑 DP 並累加。
• 邊數統計：總邊數 m = 雙覆蓋 + 單覆蓋，由餘數推導。