Изменения

<wikitex>==Определение задачи==

Иначе говоря, [[Определение сети, потока#Определение потока|закон сохранения потока]] <tex>\sum\limits_v f(u,v)=0</tex> должен выполняться для '''всех''' вершин графа, а значит нет нужды в истоке и стоке. Когда все $l_i$ равны $0$, достаточно пустить поток нулевой величины из каждой вершины, что и будет ответом. Поэтому далее в графе будут существовать ребра с положительно нижней пропускной способностью.

'''function''' circulation(<tex>V,E</tex>) <tex>G=\varnothing</tex> <font color=green>// пустой граф, вершины 0 s и n + 1 t - исток и сток, в исходном графе n вершин и m рёбер</font> '''for''' <tex>e : e\in E</tex> <font color=green>// конструктор ребра принимает 4 параметра: две инцидентные ребру вершины, величину потока через это ребро с полями (from, to, min_cap, cap)и пропускную способность</font> edge <tex>t</tex>= Edge(<tex>0s</tex>, <tex>e</tex>.to, <tex>0</tex>, <tex>e</tex>.min_cap) edge <tex>g</tex>= Edge(<tex>e</tex>.from, <tex>e</tex>.to, <tex>0</tex>, <tex>e</tex>.cap - <tex>-e</tex>.min_cap) edge <tex>h</tex>= Edge(<tex>e</tex>.from, <tex>n+1t</tex>, <tex>0</tex>, <tex>e</tex>.min_cap) <tex>G = G \cup {t,g,h}</tex> max_flow maxFlow = getmaxflowgetMaxFlow(<tex>G</tex>) <font color=green>// наибольший поток в графе G</font> '''for''' <tex>e : e\in E</tex> '''and''' <tex>e</tex>.from <tex>=s</tex> '''if''' <tex>f</tex>(<tex>e</tex>)<tex>< e</tex>.cap <font color=green>// если для текущего ребра flow < cap</font> '''return''' false '''return''' true