Изменения

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

Алгоритм масштабирования потока

165 байт добавлено, 20:22, 15 января 2011
Псевдокод
<tex>\Delta\leftarrow 2^{\lfloor\log_2U\rfloor}</tex>
'''while''' <tex>\Delta>0</tex>
'''while''' в <tex>G_f</tex> существует <tex>s-t</tex> путьс пропускной способностью большей <tex>\Delta</tex> найти <tex>P\leftarrow</tex> путь с пропускной способностью большей <tex>P\Delta</tex> <tex>\delta\leftarrow\min\{r_c_{ij}\colon(i,j)\in P\}</tex>
увеличить поток по ребрам <tex>P</tex> на <tex>\delta</tex>
обновить <tex>G_f</tex>
Анонимный участник

Навигация