Венгерский алгоритм для задачи о назначениях — в чём идея и когда применять вместо min-cost flow?

Задача о назначениях — найти совершенное паросочетание в полном двудольном графе $n\times n$ минимальной суммарной стоимости. Это частный случай min-cost max-flow, но венгерский алгоритм решает его за чистый $O(n^3)$, что обычно быстрее и проще, чем общий MCMF.

Идея (метод потенциалов / двойственность). Поддерживаем потенциалы $u_i$ (для строк) и $v_j$ (для столбцов) так, что $u_i + v_j \le cost[i][j]$ всегда. «Жёсткие» рёбра, где $u_i + v_j = cost[i][j]$, образуют граф, в котором ищем паросочетание. Если совершенное паросочетание в жёстких рёбрах найдено — оно оптимально (по двойственности ЛП). Если нет — корректируем потенциалы вдоль чередующегося дерева, добавляя новые жёсткие рёбра, и повторяем.

Компактная $O(n^3)$ реализация (формат «один столбец за итерацию», 1-индексация, матрица a[1..n][1..m], $n\le m$):

vector<int> u(n+1), v(m+1), p(m+1), way(m+1);
for(int i=1;i<=n;i++){
    p[0]=i; int j0=0;
    vector<long long> minv(m+1, LLONG_MAX);
    vector<char> used(m+1,false);
    do{
        used[j0]=true; int i0=p[j0], j1=-1; long long delta=LLONG_MAX;
        for(int j=1;j<=m;j++) if(!used[j]){
            long long cur=a[i0][j]-u[i0]-v[j];
            if(cur<minv[j]){minv[j]=cur; way[j]=j0;}
            if(minv[j]<delta){delta=minv[j]; j1=j;}
        }
        for(int j=0;j<=m;j++)
            if(used[j]){u[p[j]]+=delta; v[j]-=delta;} else minv[j]-=delta;
        j0=j1;
    } while(p[j0]!=0);
    do{int j1=way[j0]; p[j0]=p[j1]; j0=j1;} while(j0);
}
// p[j] — какая строка назначена столбцу j; стоимость = -v[0]

Асимптотика: $O(n^2 m)$, для квадратной $O(n^3)$. Память $O(nm)$.

Когда выгоднее MCMF: когда граф разреженный (не все пары допустимы) или есть нетривиальные пропускные/несбалансированные доли — там общий min-cost flow гибче. Для плотной квадратной матрицы стоимостей венгерский алгоритм — золотой стандарт.