Как свести двудольное паросочетание к задаче о максимальном потоке?
Понимаю Куна, но в разборе видел, что двудольное паросочетание — это частный случай максимального потока. Как именно строится сеть? И правда ли, что Диниц на такой сети работает быстрее, чем $O(V^2E)$?
2 ответа
Построение сети. Пусть доли $L$ и $R$.
- Добавляем суперисток $s$ и суперсток $t$.
- Из $s$ в каждую вершину $L$ — ребро пропускной способности 1.
- Из каждой вершины $R$ в $t$ — ребро пропускной способности 1.
- Каждое ребро исходного графа $l \to r$ — пропускной способности 1 (направление $L \to R$).
Максимальный поток в этой сети = размер максимального паросочетания. Рёбра $L\to R$, по которым течёт единичный поток, и образуют паросочетание. Единичные пропускные на $s\to L$ и $R\to t$ гарантируют, что каждая вершина участвует не более чем в одной паре.
// L = [0..nL), R = [nL..nL+nR), s = nL+nR, t = s+1
int S=nL+nR, T=S+1; n=T+1;
for(int l=0;l<nL;l++) add_edge(S, l, 1);
for(int r=0;r<nR;r++) add_edge(nL+r, T, 1);
for(auto&[l,r]:edges) add_edge(l, nL+r, 1);
int matching = maxflow(S, T);
Про скорость: да! На сети с единичными пропускными способностями Диниц работает за $O(E\sqrt{V})$ — это в точности оценка Хопкрофта-Карпа. Причина: число фаз ограничено $O(\sqrt{V})$ (известный результат для единичных сетей), а каждая фаза — $O(E)$. Так что «Диниц на двудольной сети» и есть Хопкрофт-Карп по сути.
Это удобно, когда у вас уже написан Диниц: не надо отдельно кодить Куна/Хопкрофта.
Маленькое предостережение: сведение к потоку даёт ту же оптимальную мощность, но если задача требует именно конкретные пары с дополнительными ограничениями (например, минимизировать суммарную стоимость пар), то обычное паросочетание уже не годится — нужен min-cost max-flow (взвешенное паросочетание / задача о назначениях). Для невзвешенного «максимум пар» поток и Кун эквивалентны по ответу; выбирайте по тому, что у вас уже реализовано и по ограничениям.