Задача об источниках и потребителях, Свести к задаче нахождения максимального потока Опции

[Maxx]

Решить задачу об источниках и потребителях, сведя ее к задаче построения максимального потока в транспортной сети и используя первый алгоритм построения максимального потока:
Данные: транспортная сеть D, заданная матрицей пропускных способностей дуг.
Результат: максимальный поток в сети.
1. Полагаем i = 0. Пусть 0 – любой допустимый поток в транспортной сети D (напри-мер, полный или нулевой).
2. По сети D и потоку i строим орграф приращений I(D, i).
3. Находим простую цепь i, являющуюся минимальным путем из v1 в vn в нагружен-ном орграфе I(D, i) (можно использовать любой описанный выше алгоритм). Если длина этой цепи равна , то поток i максимален и работа алгоритма заканчивается. В противном случае увеличиваем поток вдоль цепи i на максимально допусти-мую величину ai > 0, где aiZ (прибавляя ее для каждой дуги xX, через которую проходит цепь i, к уже имеющейся величине потока по дуге x, если дуга x входит в i, и вычитая, если дуга x* входит в i), такую, что при этом сохраняется условие до-пустимого потока. В результате меняется поток в транспортной сети D, т.е. от пото-ка i переходим к потоку i+1, который является допустимым, и при этом величина его увеличивается на ai. Присваиваем i = i + 1 и переходим к шагу 2.