Изменения
→Удаляющий обход
===Идея===
По-прежнему по одному находятся пути из <tex>s</tex> в <tex>t</tex>, но применяется следующая оптимизация: в процессе обхода в глубину удаляются все ребра, вдоль которых нельзя дойти до стока. То есть, если для текущей вершины <tex>v</tex> выполнено <tex>dfs(v) = false</tex>, нужно удалить из графа эту вершину и все инцидентные ей ребра. С точки зрения реализации, надо просто поддерживать в списке смежности каждой вершины указатель на первое неудалённое ребро, и увеличивать этот указатель в цикле внутри обхода в глубину.
int dfs (int v, int flow) {
if (!flow) return 0;
if (v == t) return flow;
for (int & to=ptr[v]; to<n; ++to) {
if (d[to] != d[v] + 1) continue;
int pushed = dfs (to, min (flow, c[v][to] - f[v][to]));
if (pushed) {
f[v][to] += pushed;
f[to][v] -= pushed;
return pushed;
}
}
return 0;
}
===Корректность===
