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

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

Крючок: вернуть пятую партию

Как думаешь, цена отмены партии равна минус цене добавления следующей? Для C(x)=x² при x=2 следующая единица стоит 9-4=5. Отмена последней возвращает 4-1=3, то есть имеет цену -3. Сумма этих двух остаточных цен равна двум. Это не противоречит тому, что «добавил и отменил» должно стоить ноль: после добавления поток будет три, а цена отмены из новой точки равна 4-9=-5. Нельзя складывать переходы, взятые из разных состояний, как будто состояние не менялось.

На что это похоже: возврат последнего билета

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

Механизм: две дуги вместо всей лестницы

После линеаризации на каждой исходной дуге оптимальный поток можно хранить как последовательность заполненных участков. Из свободных прямых участков нужен самый дешёвый, а из заполненных для отмены нужен самый дорогой. Все остальные параллельные остаточные дуги до них не понадобятся. Отсюда две текущие цены: a⁺=C(x+1)-C(x), если x0.

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

Для допустимого потока добавление единицы по направленному остаточному циклу сохраняет баланс каждой вершины. Если сумма цен отрицательна, общая стоимость уменьшается. Обратное направление доказательства использует линеаризацию: отсутствие отрицательных циклов в её остаточной сети означает оптимальность линейного потока. Спрятанные параллельные дуги не дешевле граничных, поэтому не могут создать новый отрицательный цикл, если граничная сеть его не имеет. Так получаем необходимость и достаточность критерия для целой задачи.

Правило: текущая цена относится к текущему x

Пересчитывай остаточные цены после каждого изменения потока или перехода на новый тарифный участок. Для направления i→j используем приведённую цену a-π(i)+π(j). Здесь π - потенциал вершины, то есть поправка к цене за переход между узлами. В цикле поправки сокращаются, поэтому знак полной цены цикла сохраняется.

Разбор: отмена дорогой загрузки

Две параллельные дуги перевозят три партии. Первая имеет C₁(x)=x², вторая C₂(y)=4y. Начальный план x=3,y=0 стоит девять. Остаточный цикл включает отмену единицы на первой и добавление на второй: цена (4-9)+4=-1. Меняем план на x=2,y=1; новая стоимость восемь, улучшение равно одному.

В новой точке отмена на первой стоит 1-4=-3, добавление на второй четыре, цикл стоит один. Обратный перенос стоит (9-4)-4=1. Отрицательных циклов нет. План оптимален среди целых. Если бы мы по старой цене -5 отменили ещё одну единицу, ожидали бы улучшение, но получили x=1,y=2 и цену девять. Источник ошибки - устаревший тариф.

# convex_residual.py
x = 3
y = 0
while True:
    if x == 0:
        break
    old = x*x + 4*y
    backward = (x-1)*(x-1) - x*x
    forward = 4
    cycle_cost = backward + forward
    print(x, y, old, cycle_cost)
    if cycle_cost >= 0:
        break
    x = x - 1
    y = y + 1
    new = x*x + 4*y
    assert new - old == cycle_cost
print(x*x + 4*y)
# 3 0 9 -1
# 2 1 8 1
# 8

Разбор: кратчайшие пути из псевдопотока

Псевдопоток соблюдает ёмкости, но ещё не все балансы. Пусть из s в t нужно доставить три единицы, дуги имеют цены x² и 4y. Выберем на каждой дуге индивидуальный минимум: x=y=0. При нулевых потенциалах все доступные остаточные цены неотрицательны. В s остаётся избыток три, в t дефицит три.

Первый кратчайший путь - первая дуга с ценой один. После отправки цена следующей единицы становится три. Второй путь снова первая дуга с ценой три. После него следующая единица там стоит пять, поэтому третий путь идёт по второй дуге с ценой четыре. Получаем x=2,y=1, цену восемь. Для каждого шага ограничиваем добавление избытком, дефицитом и длиной текущего тарифного участка.

В общей сети кратчайшие расстояния d от выбранной вершины избытка обновляют потенциалы по правилу π←π-d. Для остаточной дуги a-π(i)+π(j) после обновления получаем прежнюю приведённую цену+d(i)-d(j), неотрицательную по неравенству кратчайшего пути. На выбранном пути равенство, поэтому обратные дуги после дополнения тоже получают нулевые либо неотрицательные приведённые цены. При недостижимых вершинах обновление требует отдельного правила; книжная предпосылка доступных неограниченных путей устраняет этот случай. Без неё сначала нужна проверка допустимости, а не арифметика с бесконечными расстояниями.

Разбор: один цикл через несколько тарифов

Можно провести по найденному циклу несколько единиц, не прекращая работу на первом изломе. Пусть Q - предел по физическим ёмкостям и нижним границам всех дуг цикла. Обозначим F(k) полную стоимость после переноса k единиц по нему. На прямых дугах аргумент растёт, на обратных убывает. В обоих случаях выпуклость сохраняется, поэтому соседнее изменение g(k)=F(k+1)-F(k) не убывает. Ищем первую k, для которой g(k)≥0; если такой нет до Q, переносим Q. Можно останавливаться на первом нулевом приращении: дальнейшие равные по цене планы тоже оптимальны вдоль этого цикла.

Например, четыре партии сначала идут по квадратной дуге, другая имеет цену четыре за партию. После переноса k на вторую F(k)=(4-k)²+4k. Для k=0,1,2,3,4 получаем16,13,12,13,16; приращения -3,-1,1,3. Первая неотрицательная разность стоит при k=2, поэтому сразу переносим две единицы и получаем цену12. Обычный последовательный пересчёт пришёл бы к той же точке двумя шагами.

Неубывание позволяет применить двоичный поиск по k: если g(mid)<0, нужная граница правее mid; иначе она не правее mid. Правый край Q служит условной точкой остановки, в которой следующий шаг запрещён. Каждый запрос вычисляет полные цены дуг цикла в двух соседних состояниях. Поиск требует O(log Q) таких запросов, но это ускоряет только один выбранный цикл и само по себе не ограничивает число смен циклов. Нельзя вычислять все g один раз по старым остаточным ценам: при пересечении тарифов их нужно получать из исходных функций.

Что ломается при неверном начале

Если C(x)=(x-2)², нулевой поток не даёт неотрицательных остаточных цен: первая единица стоит -3. Можно начать с индивидуальных минимумов по дугам, но полученный псевдопоток может иметь новые избытки и дефициты. Алгоритм затем восстанавливает балансы кратчайшими путями. Начать с произвольного допустимого потока и просто дополнять его до нужного объёма недостаточно: в нём могут уже существовать отрицательные циклы.

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

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

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

Теперь сам

Для C(x)=x² при x=4,u=6 вычисли две остаточные цены и цены после добавления единицы. Ответ: сначала a⁺=9,a⁻=-7, после добавления x=5 получаем a⁺=11,a⁻=-9. Добавление и последующая отмена стоят 9-9=0. Приращения 9 и -7 относятся к одному исходному состоянию и не составляют последовательный замкнутый проход.