讨论/题目交流/🐱 第 7 场力扣夜喵双周赛/
🐱 第 7 场力扣夜喵双周赛

欢迎在这里交流分享你的参赛心得以及体验。

image.png

展开讨论
class Solution {
    
    private int[] id;
    private int count = 0;

    private int find(int a) {
        if (id[a] == a) return a;
        int root = find(id[a]);
        id[a] = root;
        return root;
    }

    private void union(int a, int b) {
        int aRoot = find(a);
        int bRoot = find(b);
        if (aRoot == bRoot) return;
        id[aRoot] = bRoot;
        count--;
    }

    public int minCostToSupplyWater(int n, int[] wells, int[][] pipes) {
        id = new int[n + 1];
        count = n + 1;
        for (int i = 0; i <= n; i++)
            id[i] = i;
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o[2]));
        for (int i = 0; i < wells.length; i++) {
            int[] wellPipe = {i + 1, 0, wells[i]};
            pq.offer(wellPipe);
        }
        for (int[] pipe: pipes) {
            pq.offer(pipe);
        }
        int res = 0;
        while (!pq.isEmpty() && count > 1) {
            int[] pipe = pq.poll();
            int from = pipe[0], to = pipe[1], cost = pipe[2];
            if (find(from) != find(to)) {
                res += cost;
                union(from, to);
            }
        }
        return res;
    }
}

最小生成树,把水井看成是节点与0号位置相连。

1
展开全部 2 讨论