Как решать задачу с несколькими истоками и несколькими стоками в потоке?
В задаче не один исток и сток, а несколько источников (например, склады с запасами) и несколько потребителей (магазины с потребностями). У каждого свои ограничения по объёму. Как свести это к стандартному max-flow с одним истоком и одним стоком?
2 ответа
Суперисток и суперсток. Добавляем две фиктивные вершины: суперисток $S$ и суперсток $T$.
- Из $S$ в каждый настоящий источник $s_i$ — ребро пропускной способности, равной его запасу $supply_i$ (или $\infty$, если запас не ограничен).
- Из каждого настоящего стока $t_j$ в $T$ — ребро пропускной способности, равной его потребности $demand_j$ (или $\infty$).
Теперь запускаем обычный max-flow из $S$ в $T$.
int S = N, T = N+1; n = N+2;
for(int i=0;i<srcCount;i++) add_edge(S, src[i], supply[i]);
for(int j=0;j<dstCount;j++) add_edge(dst[j], T, demand[j]);
// + исходные рёбра графа
long long flow = maxflow(S, T);
Значение потока — максимальный объём, который можно доставить с учётом всех ограничений. Если в задаче нужно проверить, можно ли полностью удовлетворить спрос, сравните поток с $\sum demand_j$: равенство значит «да».
Накладные расходы: всего +2 вершины и $O(\text{источники} + \text{стоки})$ рёбер. Асимптотика не страдает. Этот приём — стандартная «обёртка» практически для любой транспортной задачи, сводимой к потоку.
Если в задаче появляются ещё и нижние границы потока на рёбрах (например, «через канал обязано пройти не меньше $L$ единиц»), одного суперистока/суперстока уже мало — это задача о потоке с ограничениями снизу (lower bounds / feasible flow). Там используется более хитрая конструкция с дополнительными суперисточником/суперстоком и «избытками/недостатками» вершин. Но если у вас только верхние ограничения и несколько истоков-стоков — суперузлы решают всё.