25
правок
Изменения
м
'''int''' dfs('''int''' <tex>v</tex>, '''int''' flow) '''if''' (flow == 0) '''return''' 0 '''if''' (<tex>v</tex> == <tex>t</tex>) '''return''' flow '''for''' (<tex>u</tex> = ptr[<tex>v</tex>] '''to''' n) ptr[<font color=darkgreentex> // u - ссылочный типv</fonttex>]++
ptr[i] = 0;
Нет описания правки
Аналогично предыдущей идее, однако будем удалять в процессе обхода в глубину из графа все рёбра, вдоль которых не получится дойти до стока <tex>t</tex>. Это очень легко реализовать: достаточно удалять ребро после того, как мы просмотрели его в обходе в глубину (кроме того случая, когда мы прошли вдоль ребра и нашли путь до стока). С точки зрения реализации, надо просто поддерживать в списке смежности каждой вершины указатель на первое не удалённое ребро, и увеличивать этот указать в цикле внутри обхода в глубину. Корректность при этом сохраняется согласно предыдущему пункту.
'''if''' (<tex>vu \in E</tex>)
pushed = dfs(<tex>u</tex>, min(flow, c(<tex>vu</tex>) - f(<tex>vu</tex>)));
f(<tex>vu</tex>) += pushed
f(<tex>uv</tex>) -= pushed
'''return''' 0
'''main'''( )
'''...'''
flow = 0
'''for''' ('''int''' i = 1 '''to''' n)
'''do'''
pushed = '''dfs''' (<tex>s</tex>, <tex>\infty</tex>) flow += pushed;
'''while''' (pushed > 0)
