272
правки
Изменения
Нет описания правки
Оценка времени работы остальных итераций доказывается аналогично второму случаю. Количество итераций — <tex> O(\log U) </tex>. Значит, общее время работы алгоритма — <tex> O(E^2 \log U) </tex>.
}}
== Псевдокод ==
'''Max_Flow_By_Scaling(G,s,t)'''
<tex>f \leftarrow 0</tex>
<tex>\Delta \leftarrow 2^{\lfloor\log_2U\rfloor}</tex>
'''while''' <tex>\Delta \geq 1</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>
'''return''' <tex>f</tex>
== Литература ==
