Обобщённый поток: памятка

Соглашения модели

• x и ёмкость относятся к отправлению; приходит μx.
• Баланс: исходящие x минус входящие μx равен b.
• Цена за входную единицу: cx.
• Приведённая цена: c-π(i)+μπ(j).
• Петля даёт (1-μ)y: μ<1 поглощает, μ>1 создаёт приход.
• Необязательный положительный запас требует явного отвода.
• Для свободных часов петля μ=2 нужна у каждого станка.
• Внешний сток с b=0: (1-μ)y-z=0, значит μ<1.

Структура решения

Два обхода

• Потенциалы: от корня, π=f+gθ; дополнительная дуга находит θ.
• Потоки: от листьев, e=f+gθ; последний баланс находит θ.
• Сначала вычти из b вклад дуг U.
• Единственность балансов не гарантирует границы.

Один pivot

1. Найди небазисную дугу с неверным приведённым знаком.
2. Реши балансы для направления Y.
3. Пределы: (u-x)/Y при Y>0, x/(-Y) при Y<0.
4. Возьми минимум, обнови поток и базис, пересчитай потенциалы.
5. При δ=0 используй доказанное антициклическое правило.

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

• Обратный путь имеет множитель 1/μ и ограничен отменяемым потоком.
• Обычная сеть μ=1 имеет меньший ранг и базисные деревья.
• Половина самолёта - релаксация, а не план эксплуатации.
• O(m) на итерацию не означает полиномиальное полное время.
• Пищевые доли связывают переменные; чистая сеть их не восстанавливает.

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

Почему велосипед сочетает увеличивающий и поглощающий циклы? Что отличает вырождение базиса от недопустимости потока? Как проверить ответ с помощью x и π за один проход?