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