Блог пользователя al13n

Автор al13n, 13 лет назад, По-русски
Заметим, что правильная система порталов всегда либо связна, либо содержит две компоненты связности, в каждой по одному входу. Доказательство этого внизу. Кстати,  первый вариант всегда невыгоден, потому что из него можно удалить одно ребро, чтобы получить второй вариант дешевле. Построим минимальный остов графа возможных порталов. Если он содержит больше двух компонент связности, на все запросы отвечаем -1. Если содержит две, то отвечаем -1 на запросы, у которых обе вершины в одной компоненте, и вес остова на все остальные запросы. Если компонента одна, нужно уметь разбивать дерево на два так, чтобы две указанные вершины остались в разных. Это делается удалением самого тяжелого ребра в дереве на пути между этими вершинами. Находить вес этого ребра можно, если заранее подвесить дерево и найти для каждой вершины прыжки вверх по степеням двойки (как для LCA) и для каждого прыжка еще вес самого тяжелого ребра на этом пути. Тогда нетрудно расширить алгоритм посика LCA вычислением максимального веса ребра на пути между вершинами.
Доказательство первого утверждения:
Во-первых, понятно, что такая система порталов допустима: мы можем зайти через любой вход, обойти все тоннели в его компоненте связности (связности по порталам), перейти в другую компоненту (между ними есть ребро, ведь граф тоннелей связен), обойти все там, обойти оставшиеся тоннели между компонентами и выйти в одном из выходов. Теперь представим, что помимо этих двух компонент A и B есть еще какая-то C; тогда если количество ребер между A и C четно, а между B и C - нечетно, невозможно обойти все тоннели по разу и вернуться в A или B. Если выходы в одной компоненте связности, и есть еще одна компонента, то все плохо, когда тоннелей между этими компонентами нечетное количество. Доказано.
Разбор задач Codeforces Beta Round 41
  • Проголосовать: нравится
  • +15
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Я доказывал  несколько по-другому: Пусть есть некоторая вершина X не являющаяся выходом. Тогда возьмём такой граф туннелей, что вершина X имеет нечётную степень, какой-то из выходов имеет нечётную степень, а все остальные вершины имеют чётную степень. Используя портальчик можно убрать нечётность X но тогда она появится у той вершины куда ведёт портал. Единственный способ от неё избавиться - создать путь через порталы из X в какой-то выход. Значит вершина X обязательно связана с одним из выходов системой порталов.