147
правок
Изменения
м
→Поиск пути
* '''Шаг 1'''. Пусть <tex>U</tex> {{---}} корень дерева, в котором лежит <tex>S</tex>.
* '''Шаг 2'''. Если вершина <tex>U</tex> совпала с вершиной <tex>T</tex> переходим к '''шагу 6''', иначе к '''шагу 3'''.
* '''Шаг 3'''. Выберем следующее ненасыщеюнное исходящее ребро. Если ребра нет {{---}} переходим к '''шагу 7'''.Ребра рассматриваем также, как и в алгоритме Диница, с глобальным итератором. Т.е начинать просмотр будем с последнего подошедшего ребра. Если ребро не подошло {{---}} больше его не рассматриваем.
* '''Шаг 4'''. Пусть просматриваем ненасыщенное ребро, ведущее в некоторую вершину <tex>V</tex>. Подвесим корень <tex>U</tex> через это ребро к вершине <tex>V</tex>, выполнив <tex>(4)</tex> запрос.
* '''Шаг 5'''. В <tex>U</tex> записываем число, равное остаточной пропускной способности ребра. Переходим к '''шагу 1'''.
