MediumRating 2243

3419. Minimize the Maximum Edge Weight of Graph

binary-searchdepth-first-searchbreadth-first-searchgraphshortest-path

解題說明

Minimize the Maximum Edge Weight of Graph

題目描述：給定一個有向加權圖，包含 n 個節點和若干條邊。你可以刪除一些邊，使得：(1) 從節點 0 到所有其他節點都可達；(2) 每個節點的入度最多為 threshold。在滿足條件的所有方案中，最小化保留邊的最大權重。若無法滿足則回傳 -1。

解題思路：二分搜尋答案 W（最大邊權）。對於給定的 W，只保留權重 <= W 的邊，然後檢查是否存在一個子圖使得 (1) 節點 0 可達所有節點，且 (2) 每個節點入度 <= threshold。從節點 0 出發做 BFS/DFS，使用貪心策略：對每個節點，選擇權重最小的入邊（以最小化對 threshold 的使用）。若所有節點都可達且入度限制可滿足，則 W 可行。

C++ 解法

複雜度分析

時間複雜度：O((V + E) × log E) — 二分搜尋 O(log E) 次，每次 BFS 為 O(V + E)。

空間複雜度：O(V + E) — 鄰接表和 BFS 佇列。

虛擬碼

1. Collect and sort all unique edge weights
2. Binary search on weight W:
   a. Build graph using only edges with weight <= W
   b. BFS from node 0
   c. If all n nodes are reachable: W is feasible, try smaller
   d. Else: try larger W
3. Return the minimum feasible W, or -1

其他解法

Kruskal 類排序法 O(E log E)：將所有邊按權重排序，依序加入邊（類似 Kruskal），每次加入後檢查 0 是否可達所有節點且入度限制滿足。找到第一個滿足的時刻即為答案。

Dijkstra 瓶頸路徑 O((V + E) log V)：從節點 0 出發做最小瓶頸路徑（minimax path），找出到每個節點的最小化最大邊權路徑。答案為所有瓶頸值的最大值。

延伸思考

如果 threshold 對每個節點不同（每個節點有自己的入度限制），問題如何變化？
如果圖是無向的，解法是否可以簡化？
如果不是最小化最大邊權而是最小化邊權總和，問題變成什麼經典問題？

Minimize the Maximum Edge Weight of Graph — CaffeCode