Int costRto(int v)

{ return from(v)? -pcost: pcost; }

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

Свойство 22.23. Максимальный поток является максимальным потоком минимальной стоимости (mincost maxflow) тогда и только тогда, если его остаточная сеть не содер­жит (ориентированного) цикла с отрицательной стоимостью.

Доказательство: Предположим, что задан максимальный поток минимальной стоимо­сти, остаточная сеть которого содержит цикл с отрицательной стоимостью. Пусть х есть пропускная способность ребра с минимально пропускной способностью в цик­ле. Увеличим поток, добавляя х в ребра в потоке, соответствующем ребрам с положи­тельной стоимостью в остаточной сети (прямые ребра) и вычитая х из ребер, соответ­ствующих ребрам с отрицательной стоимостью в остаточной сети (обратные ребра). Эти изменения не оказывают влияния на разность между притоком и истечением лю­бой вершины, однако они меняют стоимость сети на стоимость цикла, умноженную на х, которая принимает отрицательное значение, что противоречит условию, соглас­но которому стоимость исходного потока минимальна.

Чтобы доказать обратное, предположим, что существует максимальный поток F без циклов отрицательной стоимости, стоимость которых не является минимальной, и рассмотрим любой максимальный поток М с минимальной стоимостью. В силу рас­суждений, аналогичных использованным при доказательстве теоремы о разложении потоков (свойство 22.2), мы можем найти самое большее Е ориентированных циклов таких, что добавление этих циклов к потоку F дает поток М. Тем не менее, посколь­ку F не имеет отрицательных циклов, эта операция не может понизить стоимости по­тока F, т.е. получаем противоречие. Другими словами, мы должны быть способными преобразовать F в М за счет наращивания циклов, однако мы не можем это сделать, поскольку нет циклов отрицательной стоимости, которые можно было бы использо­вать для понижения стоимости потока. ■

Это свойство немедленно приводит к простому обобщенному алгоритму решения за­дачи о потоке минимальной стоимости, получившего название алгоритма вычеркивания циклов (cycle-canceling algorithm):

Найти максимальный поток. Увеличить поток в произвольном цикле с отрицательной стоимости в остаточной сети, продолжая эту процедуру до тех пор, пока не останет­ся ни одного такого цикла.

Глава 22, Потоки в сетях

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

Поскольку мы уже разработали алгоритмы вычисления максимального потока и по­иска отрицательных циклов, мы сразу же получаем реализацию алгоритма вычеркивания циклов, представленную программой 22.9. Мы используем любую реализацию максималь­ного потока для вычисления начального максимального потока и алгоритм Беллмана-Форда поиска отрицательных циклов (см. упражнение 22.108). К двум этим реализациям в такую реализацию остается только добавить цикл, обеспечивающий наращивание пото­ков в циклах на графах.