Изменения
→Удаляющий обход
===Идея===
По-прежнему по одному находятся пути из <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;
}
