Как восстановить сами рёбра паросочетания и пути потока после запуска max-flow?
Значение максимального потока я получаю, но в задаче просят вывести сами пары паросочетания (или конкретные пути, по которым идёт поток). Как извлечь их из насыщенной остаточной сети после работы Диница? Боюсь напутать с обратными рёбрами.
2 ответа
Паросочетание. Если строили сеть из двудольного графа (рёбра $l\to r$ пропускной 1), то пара существует там, где по прямому ребру $l\to r$ прошёл поток, то есть его остаточная пропускная стала 0, а у обратного — 1.
// для каждого прямого ребра l->r (исходного графа):
for(int l=0; l<nL; l++)
for(int id : g[l]) {
int to = e[id].to;
if(to >= nL && to < nL+nR) { // это ребро в правую долю
if(e[id].cap == 0) // поток прошёл => пара
cout << l << " matched with " << to-nL << "\n";
}
}
Признак «поток прошёл» = e[id].cap == 0 для ребра, изначально имевшего cap=1. Эквивалентно: e[id^1].cap == 1 (на обратном появился остаток).
Пути потока (декомпозиция потока). Любой поток раскладывается на пути $s\to t$ (и циклы, которые можно отбросить). Жадно:
// f[id] = пущенный поток по ребру = orig_cap[id] - e[id].cap (для прямых рёбер)
vector<int> path;
while(/* есть исходящий поток из s */){
path.clear(); int v=s;
while(v != t){
for(int id : g[v]) if(!(id&1) && flowOn(id) > 0){ // прямое ребро с потоком
path.push_back(id); v = e[id].to; break;
}
}
int mn = минимум потока по рёбрам path;
for(int id : path) уменьшить flowOn(id) на mn; // "снять" путь
вывести path с величиной mn;
}
Чтобы знать пущенный поток, храните исходные пропускные orig_cap и считайте flow = orig_cap - cap для прямых рёбер. Декомпозиция работает за $O(VE)$: число путей $\le E$, каждый ищется за $O(V)$.
Грабля при декомпозиции: в остаточном потоке могут появиться циклы (если в исходной сети были рёбра туда-обратно или поток «прокрутился»). При жадном выделении путей вы можете случайно пойти по циклу и зациклить алгоритм. Защита — выделять путь только до достижения $t$ и снимать минимум вдоль него; рёбра с обнулённым потоком больше не рассматриваются. Циклы потока на величину $|f|$ не влияют, и их можно просто игнорировать. Для паросочетания этой проблемы нет (граф ацикличен по построению $s\to L\to R\to t$).