Secret Pipes (решение через графы)

Привет, сегодня поговорим про secret pipes решение через графы , обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое secret pipes решение через графы , настоятельно рекомендую прочитать все из категории Алгоритмы и теория алгоритмов.

USACO Open 2002, Green Division

Задание

Фермер Джон хочет как можно дешевле организовать свою систему распределения воды, но он не хочет, чтобы его конкурент фермер Плуто мог предсказать маршруты, которые он выбирает. Фермер Джон знает, что такая задача обычно требует самого дешевого способа прокладки труб поэтому он решил использовать второй по стоимости способ.

Дан список всех двунаправленных труб, которые могут соединять множество из W (3 <= W <= 2 000) станций с водой (каждая из которых может быть встроена в колодец). Ваша задача — найти второй из самых дешевых способов соединить насосные станции, используя не более чем Р (Р <= 20 000) труб с заданной стоимостью каждой трубы. Не должно быть трубы, соединяющей станцию саму с собой. Не должно быть двух труб, соединяющих дважды одну и ту же пару станций. Гарантируется, что есть только один самый дешевый способ распределшъ воду, и что существует, как минимум, два способа распределить воду. Все стоимости — положительные числа, помещающиеся в 32-битное целое. Водная станция идентифицируется своим номером — целым числом в диапазоне l..W.

Ввод

строка 1 - два разделенных пробелом целых числа, W u P; 
строки 2..P + 1 - каждая строка описывает одну трубу и содержит 3 числа, разделенных пробелом, — номера станций начала и конца трубы, а также стоимость этой трубы.

Вывод

Одна строка, содержащая целое число — вторая минимальная стоимость конструирования системы распределения воды.

Пример ввода:       Пример вывода: 
5 7                 20
1 2 3 
2 3 4 
1 4 7 
2 4 11 
2 5 9 
5 4 5 
3 5 8 

Решение     [вверх]

В данной задаче мы можем рассматривать насосные станции как вершины; трубы, соединяющие насосные станции — как ребра, а стоимость труб — как веса ребер. Об этом говорит сайт https://intellect.icu . Тогда по условию задачи от нас требуется построить второе по весу остовное дерево.

Теперь решение задачи можно обеспечить следующим образом.
1. Найдем минимальное остовное дерево. 
2. "Удаляя" в цикле по очереди одно из найденных ребер минимального остовного дерева и достраивая оставшийся нецельным остов до минимального остовного дерева, вычисляем стоимости получающихся деревьев и запоминаем меньшую.

Для нахождения минимального остовного дерева используем алгоритм Крускала.

Формальное описание     [вверх]

Pipes()
1. Считать из файла список ребер графа.
2. Отсортировать ребра графа по возрастанию их веса (цены трубы).
3. Использовать алгоритм Крускаля для нахождения наименьшего остового 
   дерева (выполнить пп. 3.1-3.3):
   3.1. Инициализировать значение длины дерева 0.
   3.2. Выбрать первое ребро графа в списке.
   3.3. Пока не просмотрены все ребра графа, повторять пп. 3.3.1-3.3.3:
        3.3.1. Если вершины текущего ребра не лежат в одной компоненте 
               связности, то добавить ребро в наименьшее остовое дерево.
        3.3.2. Если ребро было добавлено, то прибавить к длине дерева 
               значение веса добавленного ребра.
        3.3.3. Перейти к следующему ребру.
4. Для каждого ребра из наименьшего остового дерева выполнять пп. 4.1.-4.2:
   4.1. Найти минимальное остовое дерево по алгоритму Крускаля, 
        не используя текущее ребро.
   4.2. Если построенное дерево имеет длину, меньше минимальной для 
        остового дерева, то считать это остовое дерево вторым по весу.
5. Вывести длину второго по весу остового дерева.

На этом все! Теперь вы знаете все про secret pipes решение через графы , Помните, что это теперь будет проще использовать на практике. Надеюсь, что теперь ты понял что такое secret pipes решение через графы и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Алгоритмы и теория алгоритмов