POJ 1639：度受限最小生成樹（K度限MST）

問題陳述

給定無向圖，求最小生成樹，且頂點 v0（Park）的度 ≤ K。

解題策略

1. 忽略 v0，先求 v1..v(n-1) 的 MST，權重為 base。
2. 若 K=1：答案 = base + min(edge(v0, vi))。
3. 1 < d ≤ K：嘗試逐條加入邊 (v0, vi)，必形成環，刪除環中權重最大的非 v0 邊，更新 MST。重複直到度數達到 K 或無改進。

關鍵數據結構

• graph[V][V]：鄰接矩陣存邊權。
• edges[]：當前 MST 的邊集（不含 v0 相連邊）。
• visited[i]：標記 (v0, vi) 是否已在 MST 中。

核心步驟

// 1. Prim 求 v1..v(n-1) 的 MST
int Prim(int vertexNum) { ... }

// 2. 尋找環中最大邊（遞歸 DFS）
bool isCycle;
void maxWeightInCycle(int target, int from, int to, int& maxW, int& maxId) {
    if (to == target) { isCycle = true; return; }
    for (each edge in MST incident to 'to' except 'from') {
        maxWeightInCycle(target, to, next, maxW, maxId);
        if (isCycle) {
            if (edge.weight > maxW && edge不含v0) { maxW = edge.weight; maxId = idx; }
            break;
        }
    }
}

// 3. 主循環：最多加入 K-1 條 v0 相連邊
for (int iter = 1; iter < K; ++iter) {
    找最小增益邊 (v0, u) 使 (edge(v0,u) - maxEdgeInCycle) 最小；
    若增益 ≥ 0 break;
    將 maxEdgeInCycle 替換為 (v0, u)；
    更新 edges[]、visited[]、totalWeight；
}

複雜度

• Prim O(V²)（V ≤ 20）。
• 每次加邊 DFS O(V)，共 O(KV)。
• 總體 O(V² + KV)，極快。

關鍵細節

• 環中最大邊必須不含 v0，否則會破壞度限制。
• 圖可能不連通，需檢查 MST 是否覆蓋所有頂點。
• 邊權用 INF = 1<<30 表示不存在。

此題展示了「先構建基礎 MST，再通過局部交換優化受約束解」的經典套路。