Min-cost max-flow: как реализовать поток минимальной стоимости через Беллмана-Форда?

Идея (SSP — successive shortest paths). Вместо «любого» увеличивающего пути на каждом шаге берём кратчайший по стоимости путь $s\to t$ в остаточной сети и пускаем по нему максимум потока. Поскольку каждый раз добавляем дешевейший путь, суммарная стоимость минимальна для каждого достигнутого значения потока.

Ловушка: у обратных рёбер стоимость отрицательная ($-cost$ прямого) — это «возврат денег» при откате. Из-за отрицательных рёбер Дейкстра напрямую не годится; используем Беллмана-Форда / SPFA (или Дейкстру с потенциалами Джонсона).

struct Edge{int to; long long cap, cost; int rev;};
vector<vector<Edge>> g; int n;
void add_edge(int u,int v,long long cap,long long cost){
    g[u].push_back({v,cap,cost,(int)g[v].size()});
    g[v].push_back({u,0,-cost,(int)g[u].size()-1});
}
pair<long long,long long> mcmf(int s,int t){
    long long flow=0, cost=0;
    while(true){
        vector<long long> dist(n, LLONG_MAX);
        vector<int> pv(n,-1), pe(n,-1);
        vector<char> inq(n,0);
        deque<int> q; dist[s]=0; q.push_back(s);
        while(!q.empty()){ // SPFA
            int v=q.front(); q.pop_front(); inq[v]=0;
            for(int i=0;i<(int)g[v].size();i++){
                auto&e=g[v][i];
                if(e.cap>0 && dist[v]+e.cost<dist[e.to]){
                    dist[e.to]=dist[v]+e.cost; pv[e.to]=v; pe[e.to]=i;
                    if(!inq[e.to]){inq[e.to]=1; q.push_back(e.to);}
                }
            }
        }
        if(dist[t]==LLONG_MAX) break; // путей нет
        long long push=LLONG_MAX;
        for(int v=t; v!=s; v=pv[v]) push=min(push, g[pv[v]][pe[v]].cap);
        for(int v=t; v!=s; v=pv[v]){
            auto&e=g[pv[v]][pe[v]]; e.cap-=push; g[v][e.rev].cap+=push;
        }
        flow+=push; cost+=push*dist[t];
    }
    return {flow, cost};
}

Асимптотика: $O(\text{flow} \cdot E V)$ в худшем случае с Беллманом-Фордом. С потенциалами Джонсона + Дейкстрой — $O(\text{flow} \cdot E \log V)$. Все стоимости и потоки — long long.