Appearance
最大フロー（Maximum Flow）
容量付き有向グラフにおいて、始点 s から終点 t に流せる最大流量を求める問題。
特徴
| 項目 | 内容 |
|---|---|
| 用途 | 最大フロー・最小カット・二部マッチング |
| 適用条件 | 容量が非負 |
| 代表的な解法 | Dinic法 |
| 計算量 | O(V²E)（Dinic法の一般的な上界） |
考え方
各辺には流せる量の上限（容量）がある。
始点から終点まで、次の条件を満たしながら可能な限り流量を増やす。
- 各辺の流量は0以上、容量以下。
- 始点・終点以外の各頂点では、流入量と流出量が等しい。
Dinic法では、以下を繰り返す。
- BFSでレベルグラフを構築する。
- DFSで流せるだけ流す。
- 終点に到達できなくなれば終了する。
実装
cpp
#include <bits/stdc++.h>
#include <atcoder/maxflow>
using namespace std;
using namespace atcoder;
using ll = long long;
int main() {
int n, m, s, t;
cin >> n >> m >> s >> t;
mf_graph<ll> g(n);
for (int i = 0; i < m; i++) {
int u, v;
ll cap;
cin >> u >> v >> cap;
g.add_edge(u, v, cap);
}
ll ans = g.flow(s, t);
cout << ans << '\n';
}cpp
#pragma once
#include <algorithm>
#include <cassert>
#include <queue>
#include <vector>
struct Dinic {
using ll = long long;
static constexpr ll INF = 1LL << 60;
struct Edge {
int to, rev;
ll cap;
};
int n;
std::vector<std::vector<Edge>> g;
std::vector<int> level, iter;
Dinic(int n) : n(n), g(n), level(n), iter(n) {}
void add_edge(int from, int to, ll cap) {
assert(0 <= from && from < n && 0 <= to && to < n && cap >= 0);
int a = (int)g[from].size(), b = (int)g[to].size();
if (from == to) b++;
g[from].push_back({to, b, cap});
g[to].push_back({from, a, 0});
}
bool bfs(int s, int t) {
std::fill(level.begin(), level.end(), -1);
std::queue<int> q;
level[s] = 0;
q.push(s);
while (!q.empty()) {
int v = q.front();
q.pop();
for (const auto& e : g[v]) {
if (e.cap <= 0 || level[e.to] != -1) continue;
level[e.to] = level[v] + 1;
q.push(e.to);
}
}
return level[t] != -1;
}
ll dfs(int v, int t, ll f) {
if (v == t) return f;
for (int& i = iter[v]; i < (int)g[v].size(); i++) {
auto& e = g[v][i];
if (e.cap <= 0 || level[e.to] != level[v] + 1) continue;
ll d = dfs(e.to, t, std::min(f, e.cap));
if (d == 0) continue;
e.cap -= d;
g[e.to][e.rev].cap += d;
return d;
}
return 0;
}
ll flow(int s, int t) {
assert(0 <= s && s < n && 0 <= t && t < n && s != t);
ll ans = 0;
while (bfs(s, t)) {
std::fill(iter.begin(), iter.end(), 0);
while (ll f = dfs(s, t, INF)) ans += f;
}
return ans;
}
// 残余グラフでsから到達可能な頂点
std::vector<bool> min_cut(int s) const {
assert(0 <= s && s < n);
std::vector<bool> used(n);
std::queue<int> q;
used[s] = true;
q.push(s);
while (!q.empty()) {
int v = q.front();
q.pop();
for (const auto& e : g[v]) {
if (e.cap <= 0 || used[e.to]) continue;
used[e.to] = true;
q.push(e.to);
}
}
return used;
}
};使用例
入力（0-indexed、有向グラフ）
text
4 5 0 3
0 1 2
0 2 1
1 2 1
1 3 1
2 3 2出力
text
3始点0から終点3に最大3のフローを流せる。
ACL版
cpp
mf_graph<ll> g(n);
g.add_edge(0, 1, 2);
g.add_edge(0, 2, 1);
g.add_edge(1, 2, 1);
g.add_edge(1, 3, 1);
g.add_edge(2, 3, 2);
ll ans = g.flow(0, 3); // 3Dinic法
cpp
Dinic mf(4);
mf.add_edge(0, 1, 2);
mf.add_edge(0, 2, 1);
mf.add_edge(1, 2, 1);
mf.add_edge(1, 3, 1);
mf.add_edge(2, 3, 2);
ll ans = mf.flow(0, 3); // 3最小カット（Min Cut）
始点sと終点tを分断するために取り除く辺の容量の合計を最小化する問題。
最大フローの値 = 最小カットの容量
という性質がある（最大フロー最小カット定理）。
ACLでは最大フローを求めた後、次のように最小カットを取得できる。
cpp
ll ans = g.flow(s, t);
auto cut = g.min_cut(s);cut[v] は残余グラフでsから到達可能ならtrue。
最小カットを構成する辺は、cut[u] == true かつ cut[v] == false となる元の辺。
cpp
for (auto e : g.edges()) {
if (cut[e.from] && !cut[e.to]) {
// 最小カットを構成する辺
}
}典型的な応用
| 問題 | フローへの帰着 |
|---|---|
| 二部マッチング | 各頂点・辺に容量1を設定 |
| 辺素なパスの最大本数 | 各辺の容量を1にする |
| 頂点素なパス | 頂点分割を用いる |
| 最小カット問題 | 最大フロー最小カット定理 |
| 割当問題 | 始点・対象・終点を結ぶネットワークを構築 |
注意点
add_edge(u, v, cap)は有向辺。- 無向の容量付き辺を表現したい場合、通常は両方向に辺を追加する。
- 容量は非負。負の容量は指定できない。
flow(s, t)は内部の流量を更新する。flow()を再度呼ぶと、現在の状態から追加で流せる量を返す。min_cut()は最大フロー計算後に使用する。sとtは異なる頂点である必要がある。- 自前のDinic法は再帰DFSを使うため、深いグラフではスタックオーバーフローに注意する。
関連
- 二部グラフ判定
- 最小費用流
- 二部マッチング