MediumRating 1700
3607. Power Grid Maintenance
arrayhash-tabledepth-first-searchbreadth-first-searchunion-findgraphheap-priority-queueordered-set
解題說明
Power Grid Maintenance
題目描述：給定一個代表電力網路的無向圖，每個節點是一個電站，邊代表電力線路並有維護成本。部分電站可能故障（需要維修）。需要找出維修所有故障電站的最小總成本：選擇一組邊使得所有故障電站至少與一個正常運作的電站相連。
解題思路：這可以看作一個修改版的最短路問題。將所有正常運作的電站作為源點，計算從它們到每個故障電站的最短距離（邊權為維護成本）。使用多源 Dijkstra：將所有正常電站以距離 0 加入最小堆，然後擴展到所有故障電站。每個故障電站的最短距離之和即為答案。
C++ 解法
複雜度分析
時間複雜度：O((V + E) log V) — 多源 Dijkstra，與單源 Dijkstra 複雜度相同。
空間複雜度：O(V + E) — 鄰接表和距離陣列。
虛擬碼
1. Build adjacency list from edges 2. Identify faulty nodes (put in a set) 3. Multi-source Dijkstra: a. Initialize dist[i] = 0 for all non-faulty nodes, push them into min-heap b. Standard Dijkstra relaxation 4. Sum up dist[f] for all faulty nodes f 5. Return total (or -1 if any faulty node is unreachable)
其他解法
Union-Find + 排序邊：按成本排序邊，貪心地加入邊直到所有故障節點都與某個正常節點連通。類似 Kruskal MST，但目標不同（不需要完整生成樹）。
BFS（無權圖）：若所有邊權相同，可用多源 BFS 替代 Dijkstra，時間複雜度降為 O(V + E)。
延伸思考
- 如果可以選擇修復最多 m 個故障電站（而非全部），如何選擇使總成本最小？
- 若邊的維護成本會隨時間增加，如何在時間約束下規劃維護順序？
- 若電力網路是有向的（電力只能單向傳輸），問題如何變化？