ネットワーク最大流問題は、有向グラフ上で容量制限付きの辺を持つネットワークにおいて、ソース（始点）からシンク（終点）へ送ることのできる最大流量を求める古典的な最適化問題である。この問題は二部マッチングや資源配分など多くの応用に利用される。

基本概念

• フローネットワーク：ソース s とシンク t を持つ有向グラフ。s からは流出のみ、t へは流入のみが許可され、他のノードでは流入量と流出量が等しい（流量保存則）。
• 許容フロー：以下の条件を満たすフロー。
  1. 容量制約：各辺 (u, v) のフロー f(u,v) は 0 ≤ f(u,v) ≤ c(u,v)
  2. 流量保存：中間ノードでは流入総量 = 流出総量
  3. 全体のフロー量 |f| = ソースからの総流出量 = シンクへの総流入量

残余ネットワークと増大道

Edmonds-Karp アルゴリズム

Ford-Fulkerson 法を BFS で実装したもの。増大道を常に最短経路で選ぶことで、多項式時間 O(V·E²) を保証する。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int MAXN = 205, MAXM = 10005;
int n, m, s, t;
ll flow[MAXN], parent_edge[MAXN];
struct Edge {
    int to;
    ll cap;
    int next;
} edges[MAXM];
int head[MAXN], edge_cnt = 1;

void add_edge(int from, int to, ll cap) {
    edges[++edge_cnt] = {to, cap, head[from]};
    head[from] = edge_cnt;
}

bool bfs() {
    fill(flow, flow + n + 1, 0);
    queue<int> q;
    q.push(s);
    flow[s] = 1e9;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = head[u]; i; i = edges[i].next) {
            int v = edges[i].to;
            if (!flow[v] && edges[i].cap) {
                flow[v] = min(flow[u], edges[i].cap);
                parent_edge[v] = i;
                q.push(v);
                if (v == t) return true;
            }
        }
    }
    return false;
}

ll edmonds_karp() {
    ll total = 0;
    while (bfs()) {
        ll f = flow[t];
        for (int v = t; v != s; ) {
            int e = parent_edge[v];
            edges[e].cap -= f;
            edges[e ^ 1].cap += f;
            v = edges[e ^ 1].to;
        }
        total += f;
    }
    return total;
}

Dinic アルゴリズム

より高速な最大流アルゴリズム。BFS で階層グラフを構築し、DFS でブロッキングフローを一度に押し流す。時間計算量は O(V²·E)。

主な最適化手法：

• 階層制限：DFS は d[v] = d[u] + 1 の辺のみを辿る
• 現在弧最適化：各ノードで最後に使った辺を記録し、無駄な探索を省く
• 残余流量枝刈り：残り流量が 0 になれば早期終了

int level[MAXN], iter[MAXN];

bool bfs_level() {
    fill(level, level + n + 1, 0);
    queue<int> q;
    q.push(s);
    level[s] = 1;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = head[u]; i; i = edges[i].next) {
            int v = edges[i].to;
            if (!level[v] && edges[i].cap) {
                level[v] = level[u] + 1;
                q.push(v);
                if (v == t) return true;
            }
        }
    }
    return false;
}

ll dfs_dinic(int u, ll pushed) {
    if (u == t) return pushed;
    for (int &i = iter[u]; i; i = edges[i].next) {
        int v = edges[i].to;
        if (level[v] == level[u] + 1 && edges[i].cap) {
            ll flow_part = dfs_dinic(v, min(pushed, edges[i].cap));
            if (flow_part) {
                edges[i].cap -= flow_part;
                edges[i ^ 1].cap += flow_part;
                return flow_part;
            }
        }
    }
    return 0;
}

ll dinic() {
    ll total = 0;
    while (bfs_level()) {
        copy(head, head + n + 1, iter);
        ll pushed;
        while ((pushed = dfs_dinic(s, 1e9))) {
            total += pushed;
        }
    }
    return total;
}

実際の実装では、DFS をスタックベースの反復処理に変更することで再帰制限を回避することも可能である。最大流の真の強みは、多様な組合せ最適化問題を統一的にモデル化できることにある。