Изменения

Аналогично предыдущей идее, однако будем удалять в процессе обхода в глубину из графа все рёбра, вдоль которых не получится дойти до стока <tex>t</tex>. Это очень легко реализовать: достаточно удалять ребро после того, как мы просмотрели его в обходе в глубину (кроме того случая, когда мы прошли вдоль ребра и нашли путь до стока). С точки зрения реализации, надо просто поддерживать в списке смежности каждой вершины указатель на первое не удалённое ребро, и увеличивать этот указать указатель в цикле внутри обхода в глубину. Корректность при этом сохраняется согласно предыдущему пункту.

'''int'''dfs('''int' (''<tex>v</tex>, '', 'int'flow''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) // ''u'' is reference value '''if''' (''vu'' <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''' pushed; ptr[<tex>v</tex>]++ '''return''' 0;

'''main''' ( )

''flow'' = 0; ptr[''i'for'] = 0, ''i('' = 'int'1...n''; i = 1 '''whileto''' (pushed n) ptr[i] = 0 '''dfsdo''' pushed = dfs('''<tex>s'''</tex>, ''INF'')<tex>\infty</tex>) flow += pushed '''while'flow'' += (pushed;> 0)

 Если обход в глубину достигает стока, насыщается как минимум одно ребро, иначе как минимум один указатель продвигается вперед. Значит один запуск обхода в глубину работает за <tex>O(V + K)</tex>, где <tex>V</tex> — число вершин в графе, а <tex>K</tex> — число продвижения указателей. Ввиду того, что всего запусков обхода в глубину в рамках поиска одного [[Блокирующий поток|блокирующего потока]] будет <tex>O(P)</tex>, где <tex>P</tex> — число рёбер, насыщенных этим блокирующим потоком, то весь алгоритм поиска блокирующего потока отработает за <tex>O(PV + \sum\limits_i{K_i})</tex>, что, учитывая, что все указатели в сумме прошли расстояние <tex>O(E)</tex>, дает асимптотику <tex>O(PV + E)</tex>. В худшем случае, когда блокирующий поток насыщает все ребрарёбра, асимптотика получается <tex>O(VE)</tex>.

Для каждой вершины вводится потенциал потока, равный максимальному дополнительному потоку, который может пройти через эту вершину. Далее запускаем цикл, на каждой итерации которого определяем вершину <tex>v</tex> с минимальным потенциалом <tex>p</tex>. Затем пускается поток величины <tex>p</tex> из истока в сток, проходящий через эту вершину. При этом если [[Дополняющая сеть, дополняющий путь|остаточная пропускная способность]] ребра равна нулю, то это ребро удаляется. Также, удаляются все вершины, у которых не остаётся ни одного входящего и/или ни одного выходящего ребра. При удалении вершины все смежные ребра рёбра удаляются.

* Для каждой вершины <tex>v</tex> вычислим входящий и исходящий потенциал: <tex>p_{in}=\sum \limits_{u} c(u, v)</tex> и <tex>p_{out}=\sum \limits_{u} c(v, u, v)</tex>. Пусть <tex>p_{in}(s)=\infty</tex> и <tex>p_{out}(t)=\infty</tex>. Определим потенциал или пропускную способность вершины в [[Определение сети, потока|сети]] <tex>p(v)=min(p_{in}(v), p_{out}(v))</tex>. Таким образом, потенциал вершины определяет максимально возможное количество потока, который может через нее неё проходить. Ясно, что через вершины с <tex>p(v)=0</tex> поток проходить не может. Следовательно, их можно удалить из [[Дополняющая сеть, дополняющий путь|вспомогательной сети]]. Удалим эти вершины и дуги, им инцидентные, обновив должным образом потенциалы вершин, смежных с удаленнымиудалёнными. Если в результате появятся новые вершины с <tex>p(v)=0</tex>, удалим рекурсивно и их. В результате во вспомогательной сети останутся только вершины с <tex>p(v)\ne0</tex>.

* На втором этапе вновь, начиная с вершины <tex>v</tex>, осуществляется подвод потока уже по входящим дугам. В результате на первом шаге недостаток потока переадресуется к узлам <tex>(k-1)</tex>-го слоя, затем <tex>(k-2)</tex>-го. И так до тех пор, пока весь потока поток величины <tex>p(v)</tex>, отправленные из вершины отправленный в вершину <tex>v</tex>, где <tex>p(v)</tex> - минимальный, не соберется в истоке <tex>s</tex>. Таким образом, поток и во вспомогательной и в основной сети увеличится на величину <tex>p</tex>.

Если информация о входящих и исходящих дугах будет храниться в виде связных списков, то для того, чтобы пропустить поток, на каждой итерации будет выполнено <tex>O(K + E_i)</tex> действий, где <tex>K= O(V)</tex> соответствует числу рёбер, для которых остаточная пропускная способность уменьшилась, но осталась положительной, а <tex>E_i</tex> — числу удалённых реберрёбер. Таким образом, для поиска блокирующего потока будет выполнено <tex>\sum\limits_i{O(K+E_i)} = O(K^2)</tex> действий. == См. также ==* [[Блокирующий поток]]* [[Схема алгоритма Диница]]

==Источникиинформации==*[http://e-maxx.ru/algo/dinic#8 e-maxx MAXimal :: algo :: Алгоритм Диница]