403
правки
Изменения
→Проталкивание (Push)
Данная операция работает следующим образом: по ребру <tex> (u, v) </tex> пропускается максимально возможный поток, то есть минимум из избытка вершины <tex> u </tex> и остаточной пропускной способности ребра <tex> (u, v) </tex>, вследствие чего избыток вершины <tex> u </tex>, остаточная пропускная способность ребра <tex> (u, v) </tex> и поток по обратному ребру <tex> (v, u) </tex> уменьшается на величину потока, а избыток вершины <tex> v </tex>, поток по ребру <tex> (u, v) </tex> и остаточная пропускная способность обратного ребра <tex> (v, u) </tex> увеличивается на эту же величину.
<pre>
Push(u, v)
d = min(e(u), c(u, v) - f(u, v));
f(u, v) += d;
f(v, u) = -f(u, v);
e(u) -= d;
e(v) += d;
</pre>
=== Подъем (Relabel) ===
