第六章 - 高频考题(困难)
1168. 水资源分配优化

题目地址(1168. 水资源分配优化)

题目描述

1
村庄内有n户人家,我们可以通过挖井或者建造水管向每家供水。
2
3
对于每户人家i,我们可以通过花费 wells[i] 直接在其房内挖水井,或者通过水管连接到其他的水井。每两户住户间铺设水管的费用通过 pipes 数组表示。 pipes[i] = [house1, house2, cost] 表示住户1到住户2间铺设水管的费用为cost。
4
5
请求出所有住户都能通水的最小花费。
6
7
示例1:
8
9
10
输入: n = 3, wells = [1,2,2], pipes = [[1,2,1],[2,3,1]]
11
输出: 3
12
解释:
13
The image shows the costs of connecting houses using pipes.
14
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.
15
提示:
16
17
1 <= n <= 10000
18
wells.length == n
19
0 <= wells[i] <= 10^5
20
1 <= pipes.length <= 10000
21
1 <= pipes[i][0], pipes[i][1] <= n
22
0 <= pipes[i][2] <= 10^5
23
pipes[i][0] != pipes[i][1]
Copied!

前置知识

  • 最小生成树

公司

  • 暂无

思路

example 1
题意,在每个城市打井需要一定的花费,也可以用其他城市的井水,城市之间建立连接管道需要一定的花费,怎么样安排可以花费最少的前灌溉所有城市。
这是一道连通所有点的最短路径/最小生成树问题,把城市看成图中的点,管道连接城市看成是连接两个点之间的边。这里打井的花费是直接在点上,而且并不是所有 点之间都有边连接,为了方便,我们可以假想一个点(root)0,这里自身点的花费可以与 0 连接,花费可以是 0-i 之间的花费。这样我们就可以构建一个连通图包含所有的点和边。 那在一个连通图中求最短路径/最小生成树的问题.
参考延伸阅读中,维基百科针对这类题给出的几种解法。
解题步骤: 1. 创建 POJO EdgeCost(node1, node2, cost) - 节点1 和 节点2 连接边的花费。 2. 假想一个root0,构建图 3. 连通所有节点和 0[0,i] - i 是节点 [1,n]0-1 是节点 01 的边,边的值是节点 i 上打井的花费 wells[i]; 4. 把打井花费和城市连接点转换成图的节点和边。 5. 对图的边的值排序(从小到大) 6. 遍历图的边,判断两个节点有没有连通 (Union-Find),
  • 已连通就跳过,继续访问下一条边
  • 没有连通,记录花费,连通节点
    1. 1.
      若所有节点已连通,求得的最小路径即为最小花费,返回
    2. 2.
      对于每次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]]
如图:
minimum cost
从图中可以看到,最后所有的节点都是连通的。
复杂度分析
  • 时间复杂度: O(ElogE) - E 是图的边的个数
  • 空间复杂度: O(E)
一个图最多有 n(n-1)/2 - n 是图中节点个数 条边 (完全连通图)

关键点分析

  1. 1.
    构建图,得出所有边
  2. 2.
    对所有边排序
  3. 3.
    遍历所有的边(从小到大)
  4. 4.
    对于每条边,检查是否已经连通,若没有连通,加上边上的值,连通两个节点。若已连通,跳过。

代码 (Java/Python3)

Java code
1
class OptimizeWaterDistribution {
2
public int minCostToSupplyWater(int n, int[] wells, int[][] pipes) {
3
List<EdgeCost> costs = new ArrayList<>();
4
for (int i = 1; i <= n; i++) {
5
costs.add(new EdgeCost(0, i, wells[i - 1]));
6
}
7
for (int[] p : pipes) {
8
costs.add(new EdgeCost(p[0], p[1], p[2]));
9
}
10
Collections.sort(costs);
11
int minCosts = 0;
12
UnionFind uf = new UnionFind(n);
13
for (EdgeCost edge : costs) {
14
int rootX = uf.find(edge.node1);
15
int rootY = uf.find(edge.node2);
16
if (rootX == rootY) continue;
17
minCosts += edge.cost;
18
uf.union(edge.node1, edge.node2);
19
// for each union, we connnect one node
20
n--;
21
// if all nodes already connected, terminate early
22
if (n == 0) {
23
return minCosts;
24
}
25
}
26
return minCosts;
27
}
28
29
class EdgeCost implements Comparable<EdgeCost> {
30
int node1;
31
int node2;
32
int cost;
33
public EdgeCost(int node1, int node2, int cost) {
34
this.node1 = node1;
35
this.node2 = node2;
36
this.cost = cost;
37
}
38
39
@Override
40
public int compareTo(EdgeCost o) {
41
return this.cost - o.cost;
42
}
43
}
44
45
class UnionFind {
46
int[] parent;
47
int[] rank;
48
public UnionFind(int n) {
49
parent = new int[n + 1];
50
for (int i = 0; i <= n; i++) {
51
parent[i] = i;
52
}
53
rank = new int[n + 1];
54
}
55
public int find(int x) {
56
return x == parent[x] ? x : find(parent[x]);
57
}
58
public void union(int x, int y) {
59
int px = find(x);
60
int py = find(y);
61
if (px == py) return;
62
if (rank[px] >= rank[py]) {
63
parent[py] = px;
64
rank[px] += rank[py];
65
} else {
66
parent[px] = py;
67
rank[py] += rank[px];
68
}
69
}
70
}
71
}
Copied!
Pythong3 code
1
class Solution:
2
def minCostToSupplyWater(self, n: int, wells: List[int], pipes: List[List[int]]) -> int:
3
union_find = {i: i for i in range(n + 1)}
4
5
def find(x):
6
return x if x == union_find[x] else find(union_find[x])
7
8
def union(x, y):
9
px = find(x)
10
py = find(y)
11
union_find[px] = py
12
13
graph_wells = [[cost, 0, i] for i, cost in enumerate(wells, 1)]
14
graph_pipes = [[cost, i, j] for i, j, cost in pipes]
15
min_costs = 0
16
for cost, x, y in sorted(graph_wells + graph_pipes):
17
if find(x) == find(y):
18
continue
19
union(x, y)
20
min_costs += cost
21
n -= 1
22
if n == 0:
23
return min_costs
Copied!

延伸阅读

大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。