LeetCode 1168. 水资源分配优化

Categories:

题目描述
思路分析
1. 解法一：最小生成树 + 虚拟节点（推荐）
相似题目

题目描述

✅ 1168. 水资源分配优化

思路分析

解法一：最小生成树 + 虚拟节点（推荐）

核心思路：

将“打井成本”视为从虚拟节点 0 到每个房屋的边权。

把这些边与 pipes 合并成一张图，对所有边做 Kruskal。

最小生成树的总代价就是供水最小成本。

复杂度分析：

时间复杂度：O((n + m) log (n + m))，其中 m 为管道数量。

空间复杂度：O(n + m)，存储边与并查集。

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

class Solution {
    public int minCostToSupplyWater(int n, int[] wells, int[][] pipes) {
        List<int[]> edges = new ArrayList<>();
        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;
        for (int[] e : edges) {
            if (uf.union(e[0], e[1])) {
                cost += e[2];
            }
        }
        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))
    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
    for _, e := range edges {
        if uf.union(e.u, e.v) {
            cost += e.w
        }
    }
    return cost
}

相似题目

题目	难度	考察点
1135. 最低成本联通所有城市	中等	最小生成树
1584. 连接所有点的最小费用	中等	最小生成树
1489. 找到最小生成树里的关键边和伪关键边	困难	最小生成树
1319. 连通网络的操作次数	中等	并查集
261. 以图判树	中等	并查集

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/16074398