Изменения
Нет описания правки
#Для каждого ребра <tex>(u,v)</tex> данной сети <tex>G</tex> зададим <tex>f(u,v) = 0</tex>.
#Построим вспомогательную сеть <tex>G_L</tex> из [[Дополняющая сеть, дополняющий путь|дополняющей сети]] <tex>G_f</tex> данного графа <tex>G</tex>. Если <tex>d[t] = \infty</tex>, остановиться и вывести <tex>f</tex>.
#[[Алгоритм поиска блокирующего потока в ациклической сети|Найдем блокирующий поток ]] <tex>f'</tex> в <tex>G_L</tex>]].
#Дополним поток <tex>f</tex> найденным потоком <tex>f'</tex> и перейдем к шагу 2.
<tex>f[u][v]</tex> {{---}} поток через ребро <tex>(uv)</tex>.
<tex>p[u]</tex> {{---}} [[Алгоритм_поиска_блокирующего_потока_в_ациклической_сети#.D0.A3.D0.B4.D0.B0.D0.BB.D1.8F.D1.8E.D1.89.D0.B8.D0.B9_.D0.BE.D0.B1.D1.85.D0.BE.D0.B4 | номер первого неудаленного ребра идущего из u]]
'''bool''' bfs():
заполняем массив d значениями, равными -1<tex>\infty</tex> d[s] = 0
Q.push(s)
'''while''' !Q.isEmpty
u = Q.pop()
'''for''' <tex>(uv) \in E(G)</tex>
'''if''' f[u][v] < c[u][v] '''and ''' d[v] != -1= <tex>\infty</tex>
d[v] = d[u] + 1
Q.push(v)
'''return''' d[t] != -1<tex>\infty</tex>
<font color="darkgreen">//поиск блокирующего потока
//v u - номер вершины
//cf - минимальная пропускная способность дополняющей сети на пройденном dfs пути</font>
'''int''' dfs(u, cf):
'''if''' u == t '''or''' cf == 0
'''return''' cf
'''for''' v = p[u] '''to''' <tex>|V(G)| - 1</tex>
'''if''' d[v] == d[u] + 1 <font color="darkgreen">//это условие эквивалентно поиску во вспомогательной слоистой сети</font>
cfmin = dfs(v, min(cf, c[u][v] - f[u][v]))
'''if''' cfmin != 0 f[u][v] += cfmin<font color="darkgreen">//насыщаем ребра по пути dfs</font> f[v][u] -= cfmin '''return''' cfmin
p[u]++
'''return''' 0
