1168. Optimize Water Distribution in a Village

leetcode hard

#array#csharp#graph#greedy#hard#hash-table#heap#leetcode#queue#tree

Task

В деревне есть n домов. Мы хотим обеспечить все дома водой, строя колодцы и прокладывая трубы.

Для каждого дома i мы можем либо построить колодец внутри него непосредственно с затратами wells[i - 1] (обратите внимание на -1 из-за нумерации с нуля), либо провести воду из другого колодца с помощью трубы. Затраты на прокладку труб между домами даны в массиве pipes, где каждый pipes[j] = [house1j, house2j, costj] представляет собой стоимость соединения дома house1j и дома house2j с помощью трубы. Соединения двунаправленные, и между одними и теми же домами могут быть несколько допустимых соединений с разными затратами.

Верните минимальные о

https://leetcode.com/problems/optimize-water-distribution-in-a-village/Figures/1168/PrimAlgDemo.gifбщие

затраты на обеспечение всех домов водой.

Пример:

Input: n = 3, wells = [1,2,2], pipes = [[1,2,1],[2,3,1]]

Output: 3

Explanation: 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.

C# solution

matched/original

using System;
using System.Collections.Generic;
public class Solution {
    public int MinCostToSupplyWater(int n, int[] wells, int[][] pipes) {
        var edgesHeap = new PriorityQueue<int[], int[]>(Comparer<int[]>.Create((a, b) => a[0] - b[0]));
        var graph = new List<List<int[]>>(n + 1);
        for (int i = 0; i < n + 1; ++i) {
            graph.Add(new List<int[]>());
        }
        
        for (int i = 0; i < wells.Length; ++i) {
            graph[0].Add(new int[] { wells[i], i + 1 });
            edgesHeap.Enqueue(new int[] { wells[i], i + 1 }, new int[] { wells[i], i + 1 });
        }
        
        foreach (var pipe in pipes) {
            int house1 = pipe[0], house2 = pipe[1], cost = pipe[2];
            graph[house1].Add(new int[] { cost, house2 });
            graph[house2].Add(new int[] { cost, house1 });
        }
        
        var mstSet = new HashSet<int> { 0 };
        int totalCost = 0;
        
        while (mstSet.Count < n + 1) {
            var edge = edgesHeap.Dequeue();
            int cost = edge[0], nextHouse = edge[1];
            if (mstSet.Contains(nextHouse)) continue;
            mstSet.Add(nextHouse);
            totalCost += cost;
            foreach (var neighborEdge in graph[nextHouse]) {
                if (!mstSet.Contains(neighborEdge[1])) {
                    edgesHeap.Enqueue(neighborEdge, neighborEdge);
                }
            }
        }
        
        return totalCost;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int MinCostToSupplyWater(int n, vector<int>& wells, int[][] pipes) {
        var edgesHeap = new PriorityQueue<int[], int[]>(Comparer<int[]>.Create((a, b) => a[0] - b[0]));
        var graph = new List<List<int[]>>(n + 1);
        for (int i = 0; i < n + 1; ++i) {
            graph.push_back(new List<int[]>());
        }
        
        for (int i = 0; i < wells.size(); ++i) {
            graph[0].push_back(new int[] { wells[i], i + 1 });
            edgesHeap.Enqueue(new int[] { wells[i], i + 1 }, new int[] { wells[i], i + 1 });
        }
        
        foreach (var pipe in pipes) {
            int house1 = pipe[0], house2 = pipe[1], cost = pipe[2];
            graph[house1].push_back(new int[] { cost, house2 });
            graph[house2].push_back(new int[] { cost, house1 });
        }
        
        var mstSet = new HashSet<int> { 0 };
        int totalCost = 0;
        
        while (mstSet.size() < n + 1) {
            var edge = edgesHeap.Dequeue();
            int cost = edge[0], nextHouse = edge[1];
            if (mstSet.Contains(nextHouse)) continue;
            mstSet.push_back(nextHouse);
            totalCost += cost;
            foreach (var neighborEdge in graph[nextHouse]) {
                if (!mstSet.Contains(neighborEdge[1])) {
                    edgesHeap.Enqueue(neighborEdge, neighborEdge);
                }
            }
        }
        
        return totalCost;
    }
}

Java solution

matched/original

class Solution {
    public int minCostToSupplyWater(int n, int[] wells, int[][] pipes) {
        PriorityQueue<int[]> edgesHeap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        List<List<int[]>> graph = new ArrayList<>(n + 1);
        for (int i = 0; i < n + 1; ++i) {
            graph.add(new ArrayList<>());
        }
        
        for (int i = 0; i < wells.length; ++i) {
            graph.get(0).add(new int[]{wells[i], i + 1});
            edgesHeap.add(new int[]{wells[i], i + 1});
        }
        
        for (int[] pipe : pipes) {
            int house1 = pipe[0];
            int house2 = pipe[1];
            int cost = pipe[2];
            graph.get(house1).add(new int[]{cost, house2});
            graph.get(house2).add(new int[]{cost, house1});
        }
        
        Set<Integer> mstSet = new HashSet<>();
        mstSet.add(0);
        
        int totalCost = 0;
        while (mstSet.size() < n + 1) {
            int[] edge = edgesHeap.poll();
            int cost = edge[0];
            int nextHouse = edge[1];
            if (mstSet.contains(nextHouse)) continue;
            mstSet.add(nextHouse);
            totalCost += cost;
            for (int[] neighborEdge : graph.get(nextHouse)) {
                if (!mstSet.contains(neighborEdge[1])) {
                    edgesHeap.add(neighborEdge);
                }
            }
        }
        
        return totalCost;
    }
}

JavaScript solution

matched/original

var minCostToSupplyWater = function(n, wells, pipes) {
    const graph = Array.from({ length: n + 1 }, () => []);
    const minHeap = new MinPriorityQueue({ priority: x => x[0] });

    for (let i = 0; i < wells.length; i++) {
        graph[0].push([wells[i], i + 1]);
        minHeap.enqueue([wells[i], i + 1]);
    }

    for (const [house1, house2, cost] of pipes) {
        graph[house1].push([cost, house2]);
        graph[house2].push([cost, house1]);
    }

    const mstSet = new Set([0]);
    let totalCost = 0;

    while (mstSet.size < n + 1) {
        const [cost, nextHouse] = minHeap.dequeue().element;
        if (mstSet.has(nextHouse)) continue;
        mstSet.add(nextHouse);
        totalCost += cost;
        for (const neighborEdge of graph[nextHouse]) {
            if (!mstSet.has(neighborEdge[1])) {
                minHeap.enqueue(neighborEdge);
            }
        }
    }

    return totalCost;
};

Python solution

matched/original

import heapq

class Solution:
    def minCostToSupplyWater(self, n: int, wells: List[int], pipes: List[List[int]]) -> int:
        graph = [[] for _ in range(n + 1)]
        minHeap = []
        
        for i, cost in enumerate(wells):
            graph[0].append((cost, i + 1))
            heapq.heappush(minHeap, (cost, i + 1))
        
        for pipe in pipes:
            house1, house2, cost = pipe
            graph[house1].append((cost, house2))
            graph[house2].append((cost, house1))
        
        mstSet = set([0])
        totalCost = 0
        
        while len(mstSet) < n + 1:
            cost, nextHouse = heapq.heappop(minHeap)
            if nextHouse in mstSet:
                continue
            mstSet.add(nextHouse)
            totalCost += cost
            for edge in graph[nextHouse]:
                if edge[1] not in mstSet:
                    heapq.heappush(minHeap, edge)
        
        return totalCost

Go solution

matched/original

import (
    "container/heap"
)

type Edge struct {
    cost, house int
}

type MinHeap []Edge

func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i].cost < h[j].cost }
func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x interface{}) {
    *h = append(*h, x.(Edge))
}
func (h *MinHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

func minCostToSupplyWater(n int, wells []int, pipes [][]int) int {
    graph := make([][]Edge, n+1)
    minHeap := &MinHeap{}
    heap.Init(minHeap)
    
    for i, cost := range wells {
        graph[0] = append(graph[0], Edge{cost, i + 1})
        heap.Push(minHeap, Edge{cost, i + 1})
    }
    
    for _, pipe := range pipes {
        house1, house2, cost := pipe[0], pipe[1], pipe[2]
        graph[house1] = append(graph[house1], Edge{cost, house2})
        graph[house2] = append(graph[house2], Edge{cost, house1})
    }
    
    mstSet := map[int]bool{0: true}
    totalCost := 0
    
    for len(mstSet) < n+1 {
        edge := heap.Pop(minHeap).(Edge)
        cost, nextHouse := edge.cost, edge.house
        if mstSet[nextHouse] {
            continue
        }
        mstSet[nextHouse] = true
        totalCost += cost
        for _, neighborEdge := range graph[nextHouse] {
            if !mstSet[neighborEdge.house] {
                heap.Push(minHeap, neighborEdge)
            }
        }
    }
    
    return totalCost
}

Explanation

Algorithm

Представление графа: Постройте список смежности для представления графа, где вершины и ребра соответствуют домам и трубам. Список смежности можно представить в виде списка списков или словаря списков.

Набор для вершин: Используйте набор для поддержания всех вершин, добавленных в окончательное минимальное остовное дерево (MST) во время его построения. С помощью набора можно определить, была ли вершина уже добавлена или нет.

Очередь с приоритетом (куча): Используйте кучу для реализации жадной стратегии. На каждом шаге определяйте лучшее ребро для добавления на основе стоимости его добавления в дерево. Куча позволяет извлекать минимальный элемент за константное время и удалять минимальный элемент за логарифмическое время. Это идеально подходит для нашей задачи повторного нахождения ребра с наименьшей стоимостью.

😎