== Алгоритм ==
Пусть дана Алгоритм масштабирования [[Определение_сети,_потока#.D0.9E.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D0.B5_.D1D0.81BF.D0.B5BE.D1.82.D0.B8BE.D0.BA.D0.B0|сетьпотока]] <tex> G </tex>{{---}} алгоритм поиска максимального потока, все ребра которой имеют целочисленную основывающийся на предположении, что [[Определение_сети,_потока#.D0.9E.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D0.B5_.D1.81.D0.B5.D1.82.D0.B8|пропускную способностьпропускные способности]]. Обозначим за <tex> U </tex> максимальную пропускную способность: <tex> U = \max\limits_{(u, v) \in E} c(u, v) </tex>всех ребер выражаются целыми числами.
Идея алгоритма заключается в нахождении путей с высокой пропускной способностью в первую очередь, чтобы сразу сильно увеличивать Пусть дана [[Определение_сети,_потока#.D0.9E.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D0.B5_.D0D1.BF81.D0.BEB5.D1.82.D0.BEB8|сеть]] <tex> G </tex>, все ребра которой имеют целочисленную пропускную способность.D0Обозначим за <tex> U </tex> максимальную пропускную способность: <tex> U = \max\limits_{(u, v) \in E} c(u, v) </tex>.BA.D0.B0| Идея алгоритма заключается в нахождении путей с высокой пропускной способностью в первую очередь, чтобы сразу сильно увеличивать поток]] по ним, а затем по всем остальным. Для этого воспользуемся масштабом <tex> \Delta </tex>. Изначально положим <tex> \Delta = 2^{\lfloor \log_2 U \rfloor} </tex>.
На каждой итерации в [[Дополняющая_сеть,_дополняющий_путь|дополняющей сети]] находим [[Дополняющая_сеть,_дополняющий_путь|дополняющие пути]] с пропускной способностью не меньшей <tex> \Delta </tex>, увеличиваем поток вдоль них.
