Изменения
→Алгоритм узкого места
===Идея===
Для каждой вершины вводится потенциал потока, равный максимальному дополнительному потоку, который может пройти через эту вершину. Далее следует цикл. На каждой его итерации определяется вершина <tex>r</tex> с минимальным потенциалом <tex>\rho</tex>. Затем пускается поток величины <tex>\rho</tex> из истока в сток, проходящий через эту вершину. При этом если остаточная пропускная способность ребра равна нулю, то это ребро удаляется. Также, удаляются все вершины, у которых не остаётся ни одного входящего и/или ни одного выходящего ребра. При удалении вершины все смежные ребра удаляются.
MPM algorithm(s, t)
for each (uv) \in E
f(uv) = 0;
Вычисляем остаточную сеть R;
Найдём вспомогательный граф L для R;
while (t \in L)
begin
while (t достижима из s в L)
begin
найдём v с миниальной пропускной способностью g;
проталкиваем g единиц потока из v в t;
проталкиваем g единиц потока из s в v;
изменяем f, L и R;
end
вычисляем новый вспомогательный граф L из R;
end
===Асимптотика===
