Слабое место сети
Сеть — аэропорты и рейсы, станции и кабели, серверы и каналы — описана связями с весами: вес — сколько рейсов, кабелей или гигабит связывают два узла. Её слабое место — набор связей наименьшего суммарного веса, после обрыва которых сеть распадается хотя бы на две части. Найдите вес слабого места. Какие именно части отделятся — неважно.
Третий тест — настоящая сеть рейсов между 21 аэропортом: вес связи двух аэропортов — сколько позывных летает между ними в обе стороны. Остальные сети придуманы.
Вход
В первой строке число узлов n и число связей m (2 ≤ n ≤ 100, 0 ≤ m ≤ 5000). Дальше m строк a b w: связь узлов a и b весом w (1 ≤ w ≤ 10⁶). Между двумя узлами может быть несколько связей; связь узла с самим собой (a = b) ничего не держит.
Выход
Наименьший суммарный вес связей, после удаления которых сеть несвязна. Если она несвязна с самого начала, ответ 0.
Примеры
Пример 1
6 8 1 2 5 2 3 5 1 3 5 4 5 5 5 6 5 4 6 5 3 4 2 1 6 1
3
Пример 2
4 2 1 2 7 3 4 1
0
Ограничения
- Время · Python
- 3000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 10 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Первое, что приходит в голову, — найти узел с наименьшей суммой весов его связей: обрежь их, и он отделится. Проверьте первый пример: каждый узел держится связями весом не меньше 10, а ответ — 3.
2Подсказка 2
Если бы были известны два узла, которые слабое место разделяет, это была бы задача о минимальном разрезе между истоком и стоком — наибольший поток. Узел-исток можно взять любой: он лежит на одной из сторон. А сток?
3Идея
Нужен глобальный минимальный разрез. Три пути: перебрать сток среди всех остальных узлов и для каждого посчитать поток (n − 1 поток); случайные сжатия Каргера с достаточным числом повторов; детерминированный алгоритм Штор — Вагнера, который здесь проще и быстрее всех. Все три описаны в статье о минимальном разрезе.
4Разбор
Штор — Вагнер работает фазами. В фазе узлы выстраиваются по одному: первый любой, а каждый следующий — тот, у кого сумма весов связей с уже выстроенными наибольшая. Пусть последними встали s и t. Тогда разрез «t против всех остальных» — минимальный среди всех разрезов, разделяющих s и t; его вес — сумма весов связей t в момент, когда t вставал в очередь. Запомним его и сольём s и t в один узел: слабое место либо разделяет их — тогда мы его уже нашли, — либо нет — тогда оно останется и после слияния. Через n − 1 фазу останется один узел, а ответ — наименьший из разрезов фаз.
Матрица весов n × n удобнее списков: слияние — сложить две строки. Параллельные связи складываются, петли выбрасываются при чтении.
4+Решение
5Сложность
n − 1 фаза, в каждой — выбор очередного узла перебором и обновление сумм: O(n²) на фазу, O(n³) всего — для ста узлов это миллион шагов. С кучей и списками смежности получается O(nm + n² log n). Перебор стока с потоком на каждый — в n раз дороже одного потока, но для таких размеров тоже успевает.
6Типичные ошибки
- Самый слабый узел. Ответ «наименьшая сумма весов связей одного узла» — это
wrong.py. Часто он верен: в сети рейсов слабое место — аэропорт с двумя позывными. Но группа узлов, плотно связанных между собой, может держаться за остальную сеть слабее любого из своих узлов, как два треугольника в первом примере. - Несвязная сеть. У каждого узла во втором примере есть связь, а ответ 0: сеть уже распалась.
- Петли. Связь узла с самим собой не надо прибавлять к его весу: она ничего не соединяет.