148
правок
Изменения
→Реализация
Таким образом, в зависимости от того, каким алгоритмом нахождения блокирующего потока мы пользовались, весь алгоритм Диница может выполняться за <tex>O(VE^2)</tex> или за <tex>O(V^2E)</tex>. Также возможно достичь асимптотики <tex>O(VE\log V)</tex>, если использовать динамические деревья Слетора и Тарьяна.
==Реализация==
bfs()
<tex>q \leftarrow empty </tex>
<tex> q.push(s) </tex>
while <tex>!q.isEmty()</tex>
for (<tex>v</tex> : (<tex>flow(u,v) > 0</tex>) <tex>and</tex> (<tex>dist[v] = 0</tex>))
<tex>dist[v] \leftarrow dist[u] + 1 </tex>
<tex>q.push(v)</tex>
<tex>q.pop()</tex>
makeGl()
<tex>dist \leftarrow </tex>0
