10
правок
Изменения
Нет описания правки
== Определение слоистой сети ==
Для начала определим для каждой вершины <tex>v</tex> данной сети <tex>G</tex> длину кратчайшего <tex>s \leadsto v</tex> пути из истока и обозначим ее <tex>d[v]</tex> (для этого можно воспользоваться [[Обход в ширину|обходом в ширину]]).<br/> В слоистую сеть включаем только те ребра <tex>(u,v)</tex> исходной сети, для которых <tex>d[u] + 1 = d[v]</tex>.
Полученная сеть ациклична, и любой <tex>s \leadsto t</tex> путь в слоистой сети является кратчайшим путём в исходной, из свойств обхода в ширину.
[[Файл:Слоистая_сеть.png|500px |thumb|center| Слоистая сеть с пятью слоями. <tex>s = 0, t = 6</tex>]]<br/> В примере ребра, обозначенные пунктиром, не входят в слоистую сеть.<br/><br/>Слоистую сеть для графа G будем называть '''вспомогательной сетью'''.
== Алгоритм ==
'''return''' d[t] != <tex>\infty</tex>
<font color="darkgreen">//поиск блокирующего потока //u {{- --}} номер вершины //cf minC {{--- }} минимальная пропускная способность дополняющей сети на пройденном dfs пути</font> '''int''' dfs(u, cfminC): '''if''' u == t '''or''' cf minC == 0 '''return''' cfminC
'''for''' v = p[u] '''to''' <tex>|V(G)| - 1</tex>
'''if''' d[v] == d[u] + 1 <font color="darkgreen">//это условие эквивалентно поиску во вспомогательной слоистой сети</font> cfmin delta = dfs(v, min(cfminC, c[u][v] - f[u][v])) '''if''' cfmin delta != 0 f[u][v] += cfmin delta <font color="darkgreen">//насыщаем ребра по пути dfs</font> f[v][u] -= cfmindelta '''return''' cfmindelta
p[u]++
'''return''' 0
'''int''' findMaxFlow():
maxFlow = 0
'''while''' bfs() <font color="darkgreen">//пересчитываем d[i], заодно проверяем достижима ли t из s</font>
заполняем p нулями
flow = dfs(s, <tex>\infty</tex>)
