네트워크 플로우

최대 유량 문제

용량이 정해진 방향 간선들로 이뤄진 네트워크에서, 소스 \(s\) 에서 싱크 \(t\)
로 흘려보낼 수 있는 흐름의 최댓값을 구하는 문제다. 각 간선 \((u, v)\)에 용량
\(c(u, v)\)가 있고, 흐름 \(f\)는 다음을 만족해야 한다.

• 용량 제약: \(0 \le f(u, v) \le c(u, v)\).
• 흐름 보존: \(s, t\)를 뺀 모든 정점에서 들어온 흐름 = 나간 흐름.

목표는 \(s\)에서 나가는 총 흐름 \(|f|\)를 최대화하는 것이다.

잔여 그래프와 증가 경로

핵심 도구는 잔여 그래프(residual graph) 다. 간선 \((u, v)\)에 현재 \(f\)만큼
흘렸다면, 그 간선의 남은 용량은 \(c - f\)이고, 동시에 역방향 간선 \((v, u)\)에
\(f\)만큼의 잔여 용량이 생긴다. 역방향 용량은 "이미 보낸 흐름을 되돌릴 수
있다"는 뜻이며, 이것이 알고리즘이 잘못 보낸 흐름을 재배치하게 해 준다.

잔여 그래프에서 \(s \to t\)로 잔여 용량이 모두 양수인 경로를 증가 경로
(augmenting path) 라 한다. 경로상의 최소 잔여 용량만큼 흘리면 총 유량이
늘어난다. 증가 경로가 없을 때까지 반복하는 것이 포드-풀커슨 방법이다.

최대 유량 최소 컷 정리

컷이란 정점을 \(s\) 쪽 집합 \(S\)와 \(t\) 쪽 집합 \(T\)로 나누는 것이고, 그 용량은
\(S \to T\)로 가는 간선들의 용량 합이다.

정리: 최대 유량의 값 = 최소 컷의 용량.

증명의 골자는 (1) 어떤 흐름도 어떤 컷의 용량을 넘을 수 없고(약한 쌍대성),
(2) 증가 경로가 더 없을 때 \(s\)에서 잔여 그래프로 도달 가능한 정점 집합 \(S\)가
용량과 흐름이 정확히 일치하는 컷을 이룬다는 것이다. 이 정리 덕분에 "최대로
보낼 수 있는 양"과 "최소 비용으로 끊는 법"이 같은 값이 된다.

정당성과 종료

증가 경로가 없으면 위 컷 논증으로 현재 흐름이 최대임이 보장된다. 정수 용량이면
매 증가가 유량을 최소 1씩 늘리므로 유한 번에 끝난다. 다만 경로 선택을 아무렇게나
하면 느릴 수 있어, BFS로 최단 증가 경로를 고르는 에드몬드-카프(\(O(VE^2)\)),
나아가 레벨 그래프와 blocking flow를 쓰는 디닉(\(O(V^2\ E)\))으로 가속한다.

무엇을 모델링할 수 있나

이분 매칭, 정점/간선 분리 제약, 프로젝트 선택(최대 가중 닫힌 집합), 이미지
분할 등 수많은 최적화 문제가 최대 유량/최소 컷으로 환원된다. 모델링 능력이
이 주제의 진짜 핵심이다.

디닉의 두 단계

디닉은 다음을 반복한다.

1. 레벨 그래프: BFS로 \(s\)에서의 거리(레벨)를 매긴다. 도달 못 하면 종료.
2. blocking flow: 레벨이 정확히 1씩 증가하는 간선만 따라 DFS로 더 이상
   못 보낼 때까지 흐름을 밀어 넣는다.

레벨 단계가 최대 \(O(V)\)번 반복되고 각 blocking flow가 \(O(VE)\)이라 전체
\(O(V^2\ E)\)다. 단위 용량 이분 매칭에서는 \(O(E\sqrt V)\)로 더 빨라진다.

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

struct Dinic {
    struct Edge { int to; ll cap; int rev; };
    vector<vector<Edge>> g;
    vector<int> level, iter;
    int n;
    Dinic(int n) : g(n), level(n), iter(n), n(n) {}

    void add_edge(int u, int v, ll c) {
        g[u].push_back({v, c, (int)g[v].size()});
        g[v].push_back({u, 0, (int)g[u].size() - 1}); // 역간선 용량 0
    }
    bool bfs(int s, int t) {
        fill(level.begin(), level.end(), -1);
        queue<int> q; level[s] = 0; q.push(s);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (auto& e : g[u])
                if (e.cap > 0 && level[e.to] < 0) {
                    level[e.to] = level[u] + 1; q.push(e.to);
                }
        }
        return level[t] >= 0;
    }
    ll dfs(int u, int t, ll f) {
        if (u == t) return f;
        for (int& i = iter[u]; i < (int)g[u].size(); i++) {
            Edge& e = g[u][i];
            if (e.cap > 0 && level[u] + 1 == level[e.to]) {
                ll d = dfs(e.to, t, min(f, e.cap));
                if (d > 0) {
                    e.cap -= d;
                    g[e.to][e.rev].cap += d;   // 역간선에 흐름 되돌림 용량
                    return d;
                }
            }
        }
        return 0;
    }
    ll max_flow(int s, int t) {
        ll flow = 0;
        while (bfs(s, t)) {
            fill(iter.begin(), iter.end(), 0);
            while (ll f = dfs(s, t, INF)) flow += f;
        }
        return flow;
    }
};

흔한 실수

• 역간선 용량 — 일반 간선의 역간선은 용량 0으로 시작한다. 무방향이면 양쪽
  모두 용량 \(c\)로 두 개를 넣는다.
• iter(현재 간선 포인터) 초기화 — blocking flow마다 iter를 0으로 리셋해야
  하지만, 한 BFS 단계 안에서는 막힌 간선을 다시 보지 않도록 유지해야 한다.
  이 포인터가 없으면 시간 복잡도가 무너진다.
• 오버플로 — 용량 합이 클 수 있으니 long long과 큰 INF를 쓴다.

모델링 패턴

최소 컷을 복원하려면 마지막 잔여 그래프에서 \(s\)로부터 BFS로 도달 가능한 집합
\(S\)를 구하고, \(S\)에서 \(S\) 밖으로 나가는 원래(정방향) 간선들이 컷을 이룬다.
네트워크 플로우는 이어지는 이분 매칭, MCMF, 고모리-후 트리의 토대다.