HardRating 2301

3600. Maximize Spanning Tree Stability with Upgrades

binary-searchgreedyunion-findgraphminimum-spanning-tree

解題說明

Maximize Spanning Tree Stability with Upgrades

題目描述：給定一個 n 個節點的無向加權圖，每條邊有一個穩定度值。可以選擇最多 k 條邊進行「升級」，升級後該邊的穩定度增加到其升級值。目標是找到一棵生成樹，使得生成樹中穩定度最小的邊盡可能大（即最大化生成樹的最小邊穩定度）。

解題思路：對答案進行二分搜尋。二分搜尋最小穩定度的目標值 mid，然後驗證：是否能選出 n-1 條邊形成生成樹，其中每條邊的穩定度 >= mid，且升級的邊數 <= k。驗證時，對邊進行分類：穩定度本身 >= mid 的為「免費邊」，升級後穩定度 >= mid 的為「需升級邊」，其餘不可用。用貪心策略：優先使用免費邊（用 Union-Find 合併），然後使用需升級邊（消耗升級配額），檢查是否能構成生成樹。

C++ 解法

複雜度分析

時間複雜度：O(E * log(maxStability) * α(n)) — 二分搜尋 O(log(maxStability)) 層，每層掃描所有邊並做 Union-Find 操作（α(n) 近似常數）。

空間複雜度：O(n + E) — Union-Find 陣列和邊分類的額外空間。

虛擬碼

1. Binary search on answer value `mid` (range: 0 to max stability)
2. For each `mid`, validate:
   a. Classify edges: free (stability >= mid), upgrade (upgradedStability >= mid), unusable
   b. Initialize Union-Find with n components
   c. Add all free edges (union if connecting different components)
   d. Add upgrade edges (union if connecting, count used upgrades)
   e. Valid if components == 1 AND used <= k
3. Return the maximum valid `mid`

其他解法

Kruskal 排序法：將所有邊按穩定度排序（升級和不升級分別考慮），嘗試用 modified Kruskal 從大到小加入邊。需要動態規劃決定哪些邊升級。比二分搜尋更直接但實作更複雜。

參數搜尋 + 最大生成樹：固定升級方案後，問題變為最大瓶頸生成樹。可以枚舉升級組合，但 C(E,k) 太大。二分搜尋 + 貪心驗證是更實用的方法。

延伸思考

如果每條邊的升級有不同的成本（而非統一消耗 1 次配額），問題如何建模？
如果要同時最大化最小邊和最小化最大邊（帶寬均衡），如何修改目標函數？
在動態圖中（邊可以被添加或刪除），如何維護最優生成樹？

Maximize Spanning Tree Stability with Upgrades — CaffeCode