최소 비용 최대 유량

SPFA 기반 MCMF — 비용까지 최적인 유량.

플래티넘 II

1강 비용까지 최적인 유량 공식

문제 정의

각 간선에 용량뿐 아니라 단위 흐름당 비용이 붙어 있다. 소스에서 싱크로
보내는 흐름을 최대화하되, 그 최대 유량을 달성하는 방법 중 총비용을
최소화하는 것이 최소 비용 최대 유량(MCMF) 이다. 총비용은
$\sum_{(u,v)} f(u,v) \cdot \text{cost}(u,v)$ 로 정의된다.

핵심: 최소 비용 증가 경로

최대 유량을 증가 경로로 늘리던 것을 그대로 따르되, 매번 잔여 그래프에서
$s \to t$ 로 가는 최단(최소 비용) 경로를 골라 흐름을 보낸다.

정리: 항상 최소 비용 증가 경로로 흘리면, 각 유량 값에서 비용이 최소인
흐름을 유지한다. 따라서 더 이상 증가 경로가 없을 때(=최대 유량) 비용도
최소다.

직관은 다음과 같다. 현재 흐름이 그 유량에서 최소 비용이라고 가정하면, 잔여
그래프에는 음수 비용 사이클이 없다(있다면 그걸 따라 비용을 더 줄일 수 있어
가정에 모순). 음수 사이클이 없으면 최단 경로가 잘 정의되고, 그 경로로 흘린
새 흐름도 다음 유량 값에서 최소 비용이 됨이 귀납적으로 보장된다.

역간선과 음수 비용

플로우처럼 잔여 그래프에 역간선을 둔다. 정방향 간선의 비용이 $$w$$ 이면,
역간선의 비용은 $$-w$$ 다(흐름을 되돌리면 비용도 환불). 이 음수 비용 때문에
단순 다익스트라를 바로 쓸 수 없고, SPFA(벨만-포드 큐 최적화) 로 최단 경로를
찾는 것이 가장 흔한 구현이다.

복잡도

최소 비용 경로를 한 번 찾는 SPFA가 $$O(VE)$$ 이고, 증가 횟수가 최대 유량 값 $$F$$ 나
$$O(VE)$$ 에 비례할 수 있어 일반적으로 $O(F \cdot VE)$ 수준이다. 음수 간선을
존슨식 퍼텐셜로 보정하면 매 반복을 다익스트라( $O(E \log V)$ )로 바꿔
$O(F \cdot E \log V)$ 로 줄일 수 있다.

무엇을 모델링하나

"최대한 많이 짝지으면서 비용 최소", "정해진 개수만큼 보내되 비용 최소"(소스
용량을 $$k$$ 로 제한), 작업 배정의 가중치판인 할당 문제 등이 MCMF로 환원된다.
가중 이분 매칭은 MCMF의 대표적 특수 사례다.

2강 SPFA 기반 구현 공식

MCMF 레퍼런스 (SPFA)

각 간선에 비용을 추가하고, 매 반복마다 SPFA로 최소 비용 증가 경로를 찾아
보낼 수 있는 최대 흐름을 한꺼번에 민다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;

struct MCMF {
    struct Edge { int to; ll cap, cost; int rev; };
    vector<vector<Edge>> g;
    int n;
    MCMF(int n) : g(n), n(n) {}

    void add_edge(int u, int v, ll cap, ll 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<ll,ll> run(int s, int t) {
        ll total_flow = 0, total_cost = 0;
        while (true) {
            vector<ll> dist(n, INF);
            vector<int> pv(n, -1), pe(n, -1);
            vector<bool> inq(n, false);
            dist[s] = 0; queue<int> q; q.push(s); inq[s] = true;
            while (!q.empty()) {                 // SPFA
                int u = q.front(); q.pop(); inq[u] = false;
                for (int i = 0; i < (int)g[u].size(); i++) {
                    auto& e = g[u][i];
                    if (e.cap > 0 && dist[u] + e.cost < dist[e.to]) {
                        dist[e.to] = dist[u] + e.cost;
                        pv[e.to] = u; pe[e.to] = i;
                        if (!inq[e.to]) { q.push(e.to); inq[e.to] = true; }
                    }
                }
            }
            if (dist[t] == INF) break;            // 더 증가 경로 없음
            ll f = INF;                           // 경로상 최소 잔여 용량
            for (int v = t; v != s; v = pv[v])
                f = min(f, g[pv[v]][pe[v]].cap);
            for (int v = t; v != s; v = pv[v]) {
                auto& e = g[pv[v]][pe[v]];
                e.cap -= f; g[v][e.rev].cap += f; // 흐름 반영
            }
            total_flow += f;
            total_cost += f * dist[t];
        }
        return {total_flow, total_cost};
    }
};

흔한 실수

역간선 비용 부호 — 정방향 $$+w$$ , 역방향 $$-w$$ . 부호를 빼먹으면 흐름 되돌림
비용이 틀려 답이 어긋난다.
음수 간선에 다익스트라 — 원본 비용에 음수가 있으면 보정 없이 다익스트라를
쓰면 안 된다. SPFA를 쓰거나 퍼텐셜로 보정하라.
비용 누적 오버플로 — 유량 $\times$ 비용이 커질 수 있으니 long long.
정해진 유량만 보내기 — "정확히 $$k$$ 만 흘려라"면 소스 앞에 용량 $$k$$ 간선을
두거나, 비용이 음수가 되기 전까지만 증가시키는 식으로 제어한다.

모델링 패턴

문제	모델링
가중 이분 매칭(최소 비용)	매칭 그래프 간선에 비용
같은 출발/도착으로 $$k$$ 개 최소비용 경로	간선 용량 1, 비용=거리, 유량 $$k$$
일정/구간 스케줄 최적 배정	시간 슬롯을 정점으로
음수 비용으로 "이익 최대화"	비용 부호를 뒤집어 최소화로

MCMF는 "최대 유량의 제약을 지키면서 비용까지 최적"을 한 번에 다루는 강력한
모델이다. 더 빠른 변형으로는 퍼텐셜 + 다익스트라, 그리고 비용이 볼록일 때의
특수 가속이 있다. 가중 이분 매칭은 이후 헝가리안 알고리즘으로 $$O(N^3)$$ 전용
풀이도 배운다.

문제	모델링
가중 이분 매칭(최소 비용)	매칭 그래프 간선에 비용
같은 출발/도착으로 $\(k\)$ 개 최소비용 경로	간선 용량 1, 비용=거리, 유량 $\(k\)$
일정/구간 스케줄 최적 배정	시간 슬롯을 정점으로
음수 비용으로 "이익 최대화"	비용 부호를 뒤집어 최소화로