MediumRating 1642
3613. Minimize Maximum Component Cost
binary-searchunion-findgraphsorting
解題說明
Minimize Maximum Component Cost
題目描述：給定一個 n 個節點的無向加權圖和整數 k，需要將圖劃分為恰好 k 個連通分量（通過移除一些邊）。每個連通分量的「成本」定義為該分量內所有節點權值之和加上分量內所有邊權之和。目標是最小化所有分量中的最大成本。
解題思路：二分搜尋答案。對最大分量成本 mid 進行二分搜尋，然後驗證是否能將圖劃分為至多 k 個分量，每個分量的成本 <= mid。驗證時，將邊按權值排序，貪心地嘗試合併節點：從小到大考慮每條邊，若加入後分量成本不超過 mid，就合併；否則跳過。最終的連通分量數 <= k 即可行。
C++ 解法
複雜度分析
時間複雜度：O(E log E + E log S * α(V)) — 排序邊 O(E log E)，二分搜尋 O(log S) 層（S 為成本總和），每層 Union-Find 操作 O(E * α(V))。
空間複雜度：O(V + E) — Union-Find 陣列和分量成本。
虛擬碼
1. Sort edges by weight (ascending)
2. Binary search on max component cost `mid`:
a. Initialize Union-Find, each node is its own component with cost = nodeValue[i]
b. For each edge (u, v, w) in sorted order:
- If u, v in same component: add w to component cost; if > mid, return false
- If merging cost[u] + cost[v] + w <= mid: merge
- Else: skip (edge becomes cut edge)
c. Return true if components <= k
3. Return minimum valid `mid`其他解法
分治 + 樹 DP：若圖是樹，可直接用 DP 決定哪些邊要切斷。但本題是一般圖，需先轉化為生成樹再處理。
暴力枚舉切邊組合：嘗試所有可能的 n-1-k 條邊保留方案。C(E, n-1-k) 太大，不可行，但展示了問題的組合本質。
延伸思考
- 如果不限制分量數 k，只要最小化最大分量成本，最優策略是什麼？
- 若邊權可以為負數（表示合併的收益），如何調整演算法？
- 若需要最小化所有分量成本的標準差（而非最大值），問題如何建模？