Пути, циклы и хороший дополненный лес

Если умеешь переносить величины через обратные дуги, переходи к «Теперь сам».

Крючок: цикл без сохранения

Как думаешь, любое движение по циклу сохраняет балансы? На обычном цикле одна отправленная единица вернётся как одна. В обобщённой сети множители 2 и 3/4 возвращают полторы. В начальной вершине появляется половина единицы. В промежуточной баланс сохраняется: сколько пришло, столько отправили. Поэтому обобщённый цикл может служить источником или поглотителем количества, а базис перестаёт быть обычным деревом.

На что это похоже: круг обменов

Представь последовательность обменников, после которой ты возвращаешься к исходной валюте. Курс полного круга равен произведению курсов. Проход назад означает обратный курс, а не отрицательное количество той же валюты. Но в остаточной сети этот обратный обмен доступен только в пределах ранее совершённого обмена. Иначе возможность отмены ошибочно превратится в новую неограниченную сделку.

Механизм: сколько действительно меняется на дугах

Для прямой дуги i→j с μ, если из i отправляем q, в j приходит μq. Для обратного шага из j в i хотим убрать q единиц прихода в j. Значит, исходный x(i,j) нужно уменьшить на q/μ; в i освобождается q/μ. Поэтому множитель обратного направления равен 1/μ, а его доступная ёмкость, измеренная в j, равна μx.

Множитель пути P - произведение μ прямых дуг, делённое на произведение μ тех дуг, которые проходим против стрелки. При δ в начале пути в конце появляется δμ(P). Ту же формулу используем для ориентированного обхода цикла W. Если μ(W)>1, цикл увеличивает количество; если меньше единицы, поглощает; если равно единице, сохраняет. При смене ориентации получаем обратное число 1/μ(W), поэтому увеличение и поглощение меняются ролями.

Чистый избыток в начале цикла равен δ(μ(W)-1). Чтобы создать заданный избыток a, нужно δ=a/(μ(W)-1), если знаменатель ненулевой. Отрицательное δ означает обратный обход, и его доступность ещё надо проверить по границам дуг. Формула описывает единственное алгебраическое изменение, но не обещает его физическую допустимость.

Правило: дерево плюс один несохраняющий цикл

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

Разбор: путь со встречной дугой

Идём из A в B по дуге A→B с μ=2, затем из B в C против дуги C→B с μ=4, затем из C в D по дуге C→D с μ=3. Отправим из A шесть. В B приходит двенадцать. Чтобы убрать эти двенадцать через отмену C→B, уменьшаем её поток на три. В C освобождаются три. Отправляем их в D, там приходит девять. Множитель пути 2·3/4=1.5, и 6·1.5=9.

Если на C→B раньше шло лишь две единицы, такой перенос недопустим. Обратная ёмкость в B равна 4·2=8; начальный перенос из A ограничен восемь делить на два, то есть четырьмя. Это показывает, почему минимум исходных ёмкостей на пути не работает: каждая дуга измеряет количество на своей шкале.

# gain_path.py
from fractions import Fraction as F
sent = F(6)
arrival_b = F(2) * sent
cancel_cb = arrival_b / F(4)
arrival_d = F(3) * cancel_cb
path_multiplier = F(2) * F(3) / F(4)
print(arrival_b, cancel_cb, arrival_d)
assert arrival_d == sent * path_multiplier
old_cb = F(2)
reverse_capacity_b = F(4) * old_cb
max_start = reverse_capacity_b / F(2)
print(max_start)
# 12 3 9
# 4

cycle_multiplier = F(3, 2)
required_excess = F(2)
delta = required_excess / (cycle_multiplier - 1)
print(delta, delta * (cycle_multiplier - 1))
# 4 2

Разбор: зачем в компоненте дополнительная дуга

Возьмём две вершины A,B с дугами A→B множителя два и B→A множителя 3/4. В A потребность два, в B баланс ноль. Обозначим x на A→B, y на B→A. Баланс B: y-2x=0, значит y=2x. Баланс A: x-(3/4)y=-2. Подстановка даёт -x/2=-2, поэтому x=4,y=8. Ограничений на ёмкость пока нет. Обе дуги нужны, их множитель цикла 1.5 создаёт две единицы избытка для покрытия потребности A.

Если удалить B→A, из y=0 и баланса B получим x=0, но потребность A не удовлетворим. Обычного дерева недостаточно. Если заменить второй множитель на 1/2, цикл станет сохраняющим: баланс A равен нулю при любом x,y=2x. Для потребности два решений нет; при нулевых балансах решений бесконечно много. Именно ненулевой коэффициент μ(W)-1 даёт однозначную подстройку общей величины.

Механизм: структура F,L,U и хранение

Разбиваем дуги на F - хороший дополненный лес, L - дуги на нуле, U - дуги на верхней границе. Сначала фиксируем потоки L и U. Затем уравнения балансов однозначно определяют значения на F. Если эти значения выходят за границы, структура недопустима, хотя лес остаётся хорошим. Если базисная дуга оказалась на границе, структура вырождена; если все базисные потоки строго внутри границ, она невырождена.

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

Что ломается при одной проверке количества дуг

Равенство |F|=|N| недостаточно. В одной компоненте могут оказаться два цикла, в другой ни одного. Общий счёт правильный, но балансы второй компоненты не получится подстроить. Даже один цикл в каждой компоненте не гарантирует хорошесть: нужно проверить его множитель. Эти две проверки понадобятся при связи леса с линейным базисом.

Зачем в работе

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

Теперь сам

Цикл имеет множитель 0.8. Какой обход создаст избыток три? Ответ: формула для выбранной ориентации даёт δ=3/(-0.2)=-15. Значит, нужно идти против выбранного направления. В обратной ориентации множитель 1.25, и требуется старт двенадцать, потому что 12·0.25=3. Разные стартовые числа относятся к противоположным обходам с разными шкалами; ограничения дуг надо проверить заново.