1168. 水資源分配優化 · ttttt

# 1168. 水資源分配優化 ## 題目地址(1168. 水資源分配優化) <https://leetcode.com/problems/optimize-water-distribution-in-a-village/> ## 題目描述 ``` <pre class="calibre18">``` 村莊內有n戶人家，我們可以通過挖井或者建造水管向每家供水。對于每戶人家i，我們可以通過花費 wells[i] 直接在其房內挖水井，或者通過水管連接到其他的水井。每兩戶住戶間鋪設水管的費用通過 pipes 數組表示。 pipes[i] = [house1, house2, cost] 表示住戶1到住戶2間鋪設水管的費用為cost。請求出所有住戶都能通水的最小花費。示例1：輸入: n = 3, wells = [1,2,2], pipes = [[1,2,1],[2,3,1]] 輸出: 3 解釋: The image shows the costs of connecting houses using pipes. The best strategy is to build a well in the first house with cost 1 and connect the other houses to it with cost 2 so the total cost is 3. 提示： 1 <= n <= 10000 wells.length == n 0 <= wells[i] <= 10^5 1 <= pipes.length <= 10000 1 <= pipes[i][0], pipes[i][1] <= n 0 <= pipes[i][2] <= 10^5 pipes[i][0] != pipes[i][1] ``` ``` ## 前置知識 - 圖 - 最小生成樹 ## 公司 - 暫無 ## 思路 ![](https://img.kancloud.cn/84/6f/846f99c2d04bd22b2bfa3c522f7ed34b_450x408.jpg) 題意，在每個城市打井需要一定的花費，也可以用其他城市的井水，城市之間建立連接管道需要一定的花費，怎么樣安排可以花費最少的前灌溉所有城市。這是一道連通所有點的最短路徑/最小生成樹問題，把城市看成圖中的點，管道連接城市看成是連接兩個點之間的邊。這里打井的花費是直接在點上，而且并不是所有點之間都有邊連接，為了方便，我們可以假想一個點`（root）0`，這里自身點的花費可以與 `0` 連接，花費可以是 `0-i` 之間的花費。這樣我們就可以構建一個連通圖包含所有的點和邊。那在一個連通圖中求最短路徑/最小生成樹的問題. 參考延伸閱讀中，維基百科針對這類題給出的幾種解法。解題步驟： 1. 創建 `POJO EdgeCost(node1, node2, cost) - 節點1 和節點2 連接邊的花費`。 2. 假想一個`root` 點 `0`，構建圖 3. 連通所有節點和 `0`，`[0,i] - i 是節點 [1,n]`，`0-1` 是節點 `0` 和 `1` 的邊，邊的值是節點 `i` 上打井的花費 `wells[i]`; 4. 把打井花費和城市連接點轉換成圖的節點和邊。 5. 對圖的邊的值排序（從小到大） 6. 遍歷圖的邊，判斷兩個節點有沒有連通（`Union-Find`）， - 已連通就跳過，繼續訪問下一條邊 - 沒有連通，記錄花費，連通節點 7. 若所有節點已連通，求得的最小路徑即為最小花費，返回 8. 對于每次`union`, 節點數 `n-1`, 如果 `n==0` 說明所有節點都已連通，可以提前退出，不需要繼續訪問剩余的邊。 > 這里用加權Union-Find 判斷兩個節點是否連通，和連通未連通的節點。舉例：`n = 5, wells=[1,2,2,3,2], pipes=[[1,2,1],[2,3,1],[4,5,7]]` 如圖： ![](https://img.kancloud.cn/72/44/72449e866d946ddadd3f068e83f716fb_1440x1080.jpg) 從圖中可以看到，最后所有的節點都是連通的。 **復雜度分析** - 時間復雜度: `O(ElogE) - E 是圖的邊的個數` - 空間復雜度: `O(E)` > 一個圖最多有 `n(n-1)/2 - n 是圖中節點個數` 條邊（完全連通圖） ## 關鍵點分析 1. 構建圖，得出所有邊 2. 對所有邊排序 3. 遍歷所有的邊（從小到大） 4. 對于每條邊，檢查是否已經連通，若沒有連通，加上邊上的值，連通兩個節點。若已連通，跳過。 ## 代碼 (`Java/Python3`) *Java code* ``` <pre class="calibre18">``` class OptimizeWaterDistribution { public int minCostToSupplyWater(int n, int[] wells, int[][] pipes) { List<EdgeCost> costs = new ArrayList<>(); for (int i = 1; i <= n; i++) { costs.add(new EdgeCost(0, i, wells[i - 1])); } for (int[] p : pipes) { costs.add(new EdgeCost(p[0], p[1], p[2])); } Collections.sort(costs); int minCosts = 0; UnionFind uf = new UnionFind(n); for (EdgeCost edge : costs) { int rootX = uf.find(edge.node1); int rootY = uf.find(edge.node2); if (rootX == rootY) continue; minCosts += edge.cost; uf.union(edge.node1, edge.node2); // for each union, we connnect one node n--; // if all nodes already connected, terminate early if (n == 0) { return minCosts; } } return minCosts; } class EdgeCost implements Comparable<EdgeCost> { int node1; int node2; int cost; public EdgeCost(int node1, int node2, int cost) { this.node1 = node1; this.node2 = node2; this.cost = cost; } @Override public int compareTo(EdgeCost o) { return this.cost - o.cost; } } class UnionFind { int[] parent; int[] rank; public UnionFind(int n) { parent = new int[n + 1]; for (int i = 0; i <= n; i++) { parent[i] = i; } rank = new int[n + 1]; } public int find(int x) { return x == parent[x] ? x : find(parent[x]); } public void union(int x, int y) { int px = find(x); int py = find(y); if (px == py) return; if (rank[px] >= rank[py]) { parent[py] = px; rank[px] += rank[py]; } else { parent[px] = py; rank[py] += rank[px]; } } } } ``` ``` *Pythong3 code* ``` <pre class="calibre18">``` class Solution: def minCostToSupplyWater(self, n: int, wells: List[int], pipes: List[List[int]]) -> int: union_find = {i: i for i in range(n + 1)} def find(x): return x if x == union_find[x] else find(union_find[x]) def union(x, y): px = find(x) py = find(y) union_find[px] = py graph_wells = [[cost, 0, i] for i, cost in enumerate(wells, 1)] graph_pipes = [[cost, i, j] for i, j, cost in pipes] min_costs = 0 for cost, x, y in sorted(graph_wells + graph_pipes): if find(x) == find(y): continue union(x, y) min_costs += cost n -= 1 if n == 0: return min_costs ``` ``` ## 延伸閱讀 1. [最短路徑問題](https://www.wikiwand.com/zh-hans/%E6%9C%80%E7%9F%AD%E8%B7%AF%E9%97%AE%E9%A2%98) 2. [Dijkstra算法](https://www.wikiwand.com/zh-hans/%E6%88%B4%E5%85%8B%E6%96%AF%E7%89%B9%E6%8B%89%E7%AE%97%E6%B3%95) 3. [Floyd-Warshall算法](https://www.wikiwand.com/zh-hans/Floyd-Warshall%E7%AE%97%E6%B3%95) 4. [Bellman-Ford算法](https://www.wikiwand.com/zh-hans/%E8%B4%9D%E5%B0%94%E6%9B%BC-%E7%A6%8F%E7%89%B9%E7%AE%97%E6%B3%95) 5. [Kruskal算法](https://www.wikiwand.com/zh-hans/%E5%85%8B%E9%B2%81%E6%96%AF%E5%85%8B%E5%B0%94%E6%BC%94%E7%AE%97%E6%B3%95) 6. [Prim's 算法](https://www.wikiwand.com/zh-hans/%E6%99%AE%E6%9E%97%E5%A7%86%E7%AE%97%E6%B3%95) 7. [最小生成樹](https://www.wikiwand.com/zh/%E6%9C%80%E5%B0%8F%E7%94%9F%E6%88%90%E6%A0%91)