Почему мой код потока даёт неправильный ответ — забыл, что обратное ребро должно иметь cap = 0?
Писал Эдмондса-Карпа сам, на простых тестах работает, а на части — поток получается больше правильного. Грешу на обратные рёбра. Добавляю их так:
void add_edge(int u, int v, int cap){
g[u].push_back(e.size()); e.push_back({v, cap});
g[v].push_back(e.size()); e.push_back({u, cap}); // ??
}
Что здесь не так?
2 ответа
Ошибка в последней строке: вы дали обратному ребру ту же пропускную способность cap, что и прямому. Так вы фактически объявили ребро двунаправленным с пропускной cap в каждую сторону, а это уже другой граф — отсюда завышенный поток.
Для стандартного ориентированного ребра $u\to v$ обратное должно стартовать с cap = 0:
void add_edge(int u, int v, int cap){
g[u].push_back(e.size()); e.push_back({v, cap});
g[v].push_back(e.size()); e.push_back({u, 0}); // обратное: 0!
}
Обратное ребро нужно не как «настоящий канал», а как механизм отката: его остаточная пропускная растёт только на величину уже пущенного по прямому ребру потока (e[i^1].cap += push). Поэтому стартует оно с нуля.
Когда же cap в обе стороны легально? Только если ребро действительно неориентированное с пропускной $cap$ в каждую сторону — тогда add_edge(u,v,cap) с обоими cap корректно моделирует $u\leftrightarrow v$. Но это надо делать осознанно, по условию задачи, а не по умолчанию. Если граф ориентированный, а вы пишете cap в обратное — получите неверный (завышенный) ответ ровно как у вас.
Удобный способ застраховаться: храните пары рёбер по индексам $i$ и $i\oplus 1$ и никогда не выставляйте cap обратному вручную в основной логике. При пуске потока всегда:
e[id].cap -= push;
e[id ^ 1].cap += push;
Этот инвариант (id^1 — всегда обратное к id) работает только если рёбра добавляются строго парами и подряд. Если перемешать порядок добавления — ^1 перестанет указывать на правильное обратное ребро, и снова получите тонкий баг. Поэтому пара рёбер всегда добавляется двумя соседними push_back.