POJ 1639 Picnic Planning：度數受限最小生成樹

POJ 1639 Picnic Planning - 最小度數限制生成樹

題意：若干人開車去公園聚會，公園停車位 k 個。人們可先開車到他人家停車，再拼車去公園。車容量無限，家庭停車位無限。求最小總行程。等價於：求最小生成樹，但公園節點度數 ≤ k。

算法步驟

1. 移除公園節點，對剩餘節點跑 MST（Prim），得到若干連通分量。
2. 每個分量選擇連接公園的最小邊，公園度數 = 分量數 cnt。累加邊權到答案。
3. 若 cnt > k，無解（但題目保證有解）。
4. 需將公園度數從 cnt 增加到 k：每次添加一條公園到非直接相連節點的邊，在樹上形成環，刪去環上權值最大的邊（非公園直連邊）。選擇使總權增量最小的操作。重複 k-cnt 次。

優化關鍵

步驟 4 朴素 O(n²) 會 TLE。優化：預計算每個節點到公園路徑上（不含公園直連邊）的最大邊權 MaxEdge[i]。添加邊 (park, i) 時，增量 = cost(park,i) - MaxEdge[i]。選增量最小者。更新後需重新計算受影響節點的 MaxEdge（僅路徑上節點）。

代碼框架

// Prim 建立初始森林
// 并查集或 father[] 記錄樹結構
// Best(i) 遞歸求 i 到公園路徑上最大邊對應節點
// 主循環：for (deg=cnt+1; deg<=k; ++deg) {
    // 遍歷所有節點找最小增量
    // 更新答案、斷開最大邊、連接新邊、更新 father/MaxEdge
// }

複雜度

Prim O(n²)，優化後度數增加階段 O(k·n) ≈ O(n²)，總體 O(n²) 可接受（n≤111）。