LeetCode 1168. 水资源分配优化
题目描述
题意分析
让每一座房子最终都能获得水：可以支付该房子的井费在当地打井，也可以支付管道费，把它与其他能获得水的房子连接。管道可以经过多座房子传水，求所有房子都有水的最低总成本。
不要求所有房子必须通过管道连成一个整体，不同连通部分可以各自打井，也可以一个部分使用多口井。必须联合比较井与管道的费用，不能先固定其中一种再补另一种。
解法：最小生成树 + 虚拟节点
核心思路
[!blue]
增加一个编号为零的虚拟水源，把在房子
i打井表示成一条边(0, i)，边权为wells[i - 1]；原有候选管道直接作为房子之间的无向边。这样打井与铺管道都变成选择付费边，可以放在一起比较。这个建模与供水要求等价。实际方案里，每个房子都能沿管道走到某口已选井，再沿井边到达零号点；反过来，新图中只要房子与零号点连通，其路径上至少经过一条井边，就能得到水。因此原问题等价于用最低费用连通这
n + 1个节点。费用非负时，连通方案中的环可以删去一条多余边而不影响连通，也不会增加总费用。所以最低成本可以由一棵生成树实现，转化成最小生成树问题。所有房子都有自己的井边可选，因此新图一定存在连通方案。
用 Kruskal 将全部边按费用升序处理，只选择连接两个不同连通块的边。它的贪心依据是：对当前某个连通块，要把它接到外面，任意最终生成树都必须有一条跨越这道分界的边；当前可选最便宜的跨块边，可以替换那个连接而不增加费用。因此每次这样合并，都能保留某个最优完成方案。
并查集用于判断两端是否已经连通。若已连通，加边只会成环，跳过且不计费；否则合并并累加费用。包含虚拟水源后共有
n + 1个节点，选入n条不成环的边就连成整棵树，可以结束。
解题步骤
- 为每座房子加入连接零号水源的井边，再加入全部候选管道边。
- 对统一边集按费用升序排序。
- 初始化容纳零号点和所有房子的并查集，费用和成功选边数都为零。
- 逐条尝试合并边的两个端点；已经连通则跳过，合并成功才计费并增加选边数。
- 成功选入
n条边后返回总成本。
代码实现
class Solution {
public int minCostToSupplyWater(int n, int[] wells, int[][] pipes) {
List<int[]> edges = new ArrayList<>();
// 打井 = 从虚拟水源 0 引一条边到该房子。
for (int i = 1; i <= n; i++) {
edges.add(new int[] {
0,
i,
wells[i - 1],
});
}
for (int[] p : pipes) {
edges.add(new int[] {
p[0],
p[1],
p[2],
});
}
Collections.sort(edges, Comparator.comparingInt(a -> a[2]));
UnionFind uf = new UnionFind(n + 1);
int cost = 0;
int used = 0;
for (int[] e : edges) {
// 合并成功才计费：失败说明两端已连通，这条边只会成环。
if (uf.union(e[0], e[1])) {
cost += e[2];
// 虚拟水源使图共有 n+1 个节点，连接它们需要 n 条边。
if (++used == n) {
break;
}
}
}
return cost;
}
static class UnionFind {
int[] parent;
int[] size;
UnionFind(int n) {
parent = new int[n];
size = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
size[i] = 1;
}
}
int find(int x) {
while (x != parent[x]) {
// 路径减半，就地把查找路径压扁。
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
boolean union(int a, int b) {
int ra = find(a);
int rb = find(b);
if (ra == rb) {
return false;
}
// 按大小合并，小树挂到大树下。
if (size[ra] < size[rb]) {
int t = ra;
ra = rb;
rb = t;
}
parent[rb] = ra;
size[ra] += size[rb];
return true;
}
}
}
import "sort"
type Edge struct {
u int
v int
w int
}
type UnionFind struct {
parent []int
size []int
}
func newUnionFind(n int) *UnionFind {
parent := make([]int, n)
size := make([]int, n)
for i := 0; i < n; i++ {
parent[i] = i
size[i] = 1
}
return &UnionFind{parent: parent, size: size}
}
func (uf *UnionFind) find(x int) int {
for x != uf.parent[x] {
// 路径减半，就地把查找路径压扁。
uf.parent[x] = uf.parent[uf.parent[x]]
x = uf.parent[x]
}
return x
}
func (uf *UnionFind) union(a, b int) bool {
ra := uf.find(a)
rb := uf.find(b)
if ra == rb {
return false
}
// 按大小合并，小树挂到大树下。
if uf.size[ra] < uf.size[rb] {
ra, rb = rb, ra
}
uf.parent[rb] = ra
uf.size[ra] += uf.size[rb]
return true
}
func minCostToSupplyWater(n int, wells []int, pipes [][]int) int {
edges := make([]Edge, 0, n+len(pipes))
// 打井 = 从虚拟水源 0 引一条边到该房子。
for i := 1; i <= n; i++ {
edges = append(edges, Edge{u: 0, v: i, w: wells[i-1]})
}
for _, p := range pipes {
edges = append(edges, Edge{u: p[0], v: p[1], w: p[2]})
}
sort.Slice(edges, func(i, j int) bool {
return edges[i].w < edges[j].w
})
uf := newUnionFind(n + 1)
cost := 0
used := 0
for _, e := range edges {
// 合并成功才计费：失败说明两端已连通，这条边只会成环。
if uf.union(e.u, e.v) {
cost += e.w
used++
// 虚拟水源使图共有 n+1 个节点，连接它们需要 n 条边。
if used == n {
break
}
}
}
return cost
}
复杂度分析
- 时间复杂度：$O((n + m)\log(n + m + 1))$，
m为候选管道数，排序全部井边和管道边占主导；并查集使用路径压缩和按大小合并。- 空间复杂度：$O(n + m)$，保存统一边集和
n + 1个节点的并查集状态。
关键点总结
[!green]
- 虚拟水源将“在哪里打井”转化为可与管道直接比较的候选边。
- 能与零号点连通，恰好等价于存在通往某口已选井的供水路径。
- Kruskal 只为跨连通块的便宜边计费，避免为成环的冗余连接付费。
- 新图比房子数量多一个节点，完成所需边数相应为
n。
易错点总结
[!yellow]
- 先固定所有管道再决定打井位置，或只打一口井，会限制原本允许的更便宜方案。
- 并查集只开
n个位置，无法同时容纳零号水源和编号为n的房子。- 用房子编号直接索引井费，忘记数组下标从零开始，应该使用
wells[i - 1]。- 合并失败仍计入费用，会为已经连通的两个端点额外支付环边。
- 选入
n - 1条边就提前停止，漏掉虚拟节点增加后仍需的一条连接。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1135. 最低成本连通所有城市 | 中等 | 把建井费用作为虚拟节点到各房子的边后，转成标准最低成本连通问题。 |
| 1584. 连接所有点的最小费用 | 中等 | 同样最小生成树，原题边权来自点距离，本题边来自管道及虚拟建井边。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！