Задача 59: Школы (XIV Всеукраинская олимпиада по информатике)
С целью подготовки к проведению
олимпиады по информатике мэр решил обеспечить надежным
электроснабжением все школы города. Для этого необходимо провести
линию электропередач от альтернативного источника электроэнергии "Майбуття"
к одной из школ города (к какой неважно), а также соединить линиями
электропередач некоторые школы между собой.
Считается, что школа имеет надежное электроснабжение, если она
напрямую связана с источником "Майбуття", либо с одной из тех школ,
которые имеют надежное электроснабжение.
Известна стоимость соединения между некоторыми парами школ. Мэр
города решил выбрать одну из двух наиболее экономичных схем
электроснабжения (стоимость схемы равняется сумме стоимостей
соединений пар школ).
Задание
Напишите программу SCHOOLS, которая вычисляет стоимость двух
наиболее экономных схем альтернативного электроснабжения школ.
Входные данные
В первой строке входного файла SCHOOLS.DAT находятся два
натуральных числа, разделенных пробелом: N (3 <= N <= 100),
количество школ в городе, и M - количество возможных соединений
между ними. В каждой из последующих M строк находятся по три числа:
Ai, Bi, Ci, разделенных пробелами, где Ci - стоимость прокладки
линии электроснабжения (1 <= Ci <= 300) от школы Ai до школы Bi (i =
1, 2, ..., N).
Пример входного файла
5 8
1 3 75
3 4 51
2 4 19
3 2 95
2 5 42
5 4 31
1 2 9
3 5 66
Выходные данные
В единственной строке выходного файла SCHOOLS.SOL должны
содержаться два натуральных числа S1 и S2, разделенных
пробелом - две наименьшие стоимости схем (S1 <= S2). S1=S2 тогда и
только тогда, когда существует несколько схем надежного
электроснабжения наименьшей стоимости.
Пример выходного файла
110 121
Решение:
Ясно, что мы имеем дело с графом, из которого нужно выделить
некоторую компоненту, такую, что каждая вершина графа входит в эту
компоненту. Сумма всех ребер этой компоненты должна быть наименьшей.
Назовем эту компоненту остовным деревом минимального веса.
Существует два основных алгоритма нахождения остовного дерева
минимального веса - алгоритм Прима (работает за O(n^2), n -
количество вершин в графе) и алгоритм Крускала (O(e*loge), e -
количество ребер в графе). Первый алгоритм реализуется проще,
поэтому задачу будем решать пользуясь им.
Цепляем электропитание к любой школе (это бесплатно, так как каждая
школа должна быть элементом дерева, то стартовой можно выбрать
любую, для определенности первую). Теперь нужно поговорить о
структуре данных, хранящую связи между школами. Я использовал две
таблицы смежности размером 100*100 (это даже в BP укладывается).
Теперь перейдем к построению остовного дерева. Обозначим множество
всех вершин буквой G, а множество вершин дерева - T. На каждом шаге
к множеству T будем присоединять одну вершину из множества G/T (G
исключая T), такую, что стоимость соединения этой вершины с T
меньше, чем стоимость соединения любой другой вершины с множеством
T. Для приведенных входных данных порядок включения вершин будет
такой: 1, 2, 4, 5, 3.
Множество вершин T можно представить в виде одной вершины, т.е.
завести для нее одномерный массив, хранящий стоимости соединения ее
с вершинами, не входящими в T. Первоначально множество связей T
будет совпадать с множеством связей первой школы, затем, выбираем из
этого множества связь с наименьшим значением (самую дешевую линию) и
добавляем к T вершину, на которую указывает эта связь. Теперь, если
для какой-либо вершины из G/T стоимость проложения линии от
добавленной вершины меньше, чем от T, то заменим стоимость
проложения линии от T до этой вершины на стоимость проложения линии
от этой вершины до вновь добавленной.
Может быть немножко путано, но я старался избежать теории, показав
только практику.
Информацию о том, от какой вершины (кроме массива со стоимостями
связей T надо хранить также массив, указывающей из какой вершины T
исходит эта связь) до какой была проложена линия будем заносить во
второю таблицу смежности.
После первого выполнения процедуры поиска мы получим первый вариант
прокладки линий во второй таблице смежности. Теперь нам нужно найти
второй вариант. Ясно, что второе остовное дерево должно отличаться
от первого, т.е. не содержать хотя бы одного ребра, которое
принадлежит второму остовному дереву. Эти мы и воспользуемся - будем
по одному удалять ребра первого остовного дерева из данного графа и
искать другое остовное минимального веса, не забывая после этого
поиска восстанавливать ребро.
Далее
ð
