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

😎 Решение:

class Solution {
    function minCostToSupplyWater($n, $wells, $pipes) {
        $graph = array_fill(0, $n + 1, []);
        $minHeap = new SplPriorityQueue();
        $minHeap->setExtractFlags(SplPriorityQueue::EXTR_DATA);
        
        foreach ($wells as $i => $cost) {
            $graph[0][] = [$cost, $i + 1];
            $minHeap->insert([$cost, $i + 1], -$cost);
        }
        
        foreach ($pipes as $pipe) {
            [$house1, $house2, $cost] = $pipe;
            $graph[$house1][] = [$cost, $house2];
            $graph[$house2][] = [$cost, $house1];
        }
        
        $mstSet = [0 => true];
        $totalCost = 0;
        
        while (count($mstSet) < $n + 1) {
            $edge = $minHeap->extract();
            [$cost, $nextHouse] = $edge;
            if (isset($mstSet[$nextHouse])) continue;
            $mstSet[$nextHouse] = true;
            $totalCost += $cost;
            foreach ($graph[$nextHouse] as $neighborEdge) {
                if (!isset($mstSet[$neighborEdge[1]])) {
                    $minHeap->insert($neighborEdge, -$neighborEdge[0]);
                }
            }
        }
        
        return $totalCost;
    }
}

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