Оценка сложности остальных итераций доказывается аналогично второму случаю. Количество итераций — <tex> O(\log U) </tex>. Значит, общая сложность алгоритма — <tex> O(E^2 \log U) </tex>.
}}
== Псевдокод ==
'''Capacity-Scaling'''
<tex> f \leftarrow 0 </tex>
<tex> \Delta \leftarrow 2^{\lfloor \log_2 U \rfloor}</tex>
'''while''' <tex> \Delta >0</tex>
'''do''' '''while''' в <tex>G_f</tex> существует <tex>s-t</tex> путь с пропускной способностью большей <tex>\Delta</tex>
'''do''' <tex>P\leftarrow</tex> путь с пропускной способностью большей <tex>\Delta</tex>
<tex>\delta\leftarrow\min\{c_{ij}\colon(i,j)\in P\}</tex>
увеличить поток по рёбрам <tex>P</tex> на <tex>\delta</tex>
обновить <tex>G_f</tex>
<tex>f\leftarrow f+\delta</tex>
<tex>\Delta\leftarrow\Delta/2</tex>
== Литература ==
