Выпуклый поток: памятка

Перед выбором алгоритма

• Цель разделима: сумма C(i,j)(x(i,j)).
• Балансы задают ровно b; верхнюю мощность задаёт ёмкость дуги.
• Потенциал дороги: производная ∫t равна t; цель x·t другая.
• Для целой задачи соседние приращения не убывают.
• Уточни: x целый или непрерывный, функция таблицей или формулой.

Формулы, которые проверяют код

• Прямая остаточная цена: C(x+1)-C(x).
• Обратная: C(x-1)-C(x), а не минус прямая.
• Блоковая цена: [C(x±Δ)-C(x)]/Δ.
• Приведённая цена: a-π(i)+π(j).
• Нет отрицательного остаточного цикла - целый поток оптимален.

Выбор представления

Проверка фазы

1. Конечные целые u включены в U; для ∞ сначала докажи границу.
2. Ремонт: старый блок существует либо новый упирается в границу.
3. Пути из S в T; потенциалы π←π-min(d,D), включая недостижимые.
4. Нет Δ-пути: уменьши масштаб; при Δ=1 проверь баланс/разрез.
5. На фазу O(m+n), O(m) после удаления изолированных вершин.

Ловушки джокера

• Целые данные не гарантируют целый непрерывный минимум квадрата.
• Таблица U приращений длиннее двоичной записи U.
• Старая цена устаревает после перемещения границы тарифа.
• Уордроп требует разрешённой малой смены маршрута и условий задержек.
• Отсутствие грубого пути ещё не доказывает недопустимость.
• Для ∞ максимума конечных ёмкостей недостаточно для старта.

Вспомни без подсказки

Почему одно исправление на Δ восстанавливает знаки после 2Δ? Как разрез R даёт границу (m+2n)Δ для остаточных избытков? Как отличить потери электрической сети от факта проводимости?