Изменения

Перейти к: навигация, поиск

Метод проталкивания предпотока

2 байта добавлено, 09:20, 25 сентября 2015
Схема алгоритма: Перепутан сток и исток
== Схема алгоритма ==
Для начала проинициализируем предпоток. Пропустим максимально возможный поток по ребрам, инцидентным стокуистоку, увеличив избыточный поток для каждой смежной со стоком с истоком вершиной на соответствующую величину. Все остальные потока не несут, следовательно, для вершин не смежных с истоком избыточный поток изначально будет нулевым. Также для всех вершин, кроме, естественно, истока, установим высоту, равную нулю.
Более формально это можно записать так:
Анонимный участник

Навигация