Задача: 1168. Optimize Water Distribution in a Village
Сложность: hard

В деревне есть 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.

👨‍💻 Алгоритм:

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

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

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

😎 Решение:

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;
    }
}

Ставь 👍 и забирай 📚 Базу знаний