最大流 (Edmonds-Kerp)
概要
Edmonds-Kerp のアルゴリズムはグラフの最大流を求める．FF との違いは増加道の選択が辺の数の意味での最短経路を選ぶという点だけ．
計算量
この実装では隣接行列を生成しているので $O(VE^2 + V^2)$．
使い方
using Flow = int し Edge 構造体に Flow cap というメンバを追加する
edmonds_kerp ek(g)- グラフ
gを組み込む edmonds_kerp ek(N)- 大きさ
Nのグラフを作る ek.add_edge(u,v,c)uからvへ容量cの辺を追加するek.solve(s,t)sからtへの最大流を求めるek.flow[u][v]- 辺 (
u,v) の流量 (solveの実行後にのみ有効)
実装
struct edmonds_kerp {
int n;
std::vector<int> prev, level;
std::vector<std::vector<Flow>> cap, flow;
std::vector<std::vector<int>> g;
Flow inf;
edmonds_kerp(int n)
: n(n),
cap(n, std::vector<Flow>(n)),
flow(n, std::vector<Flow>(n)),
g(n, std::vector<int>()),
inf(std::numeric_limits<Flow>::max() / 8) {}
edmonds_kerp(const Graph &graph) {
*this = edmonds_kerp(graph.size());
rep(i, n) for (auto &e : graph[i]) add_edge(e.src, e.dst, e.cap);
}
void add_edge(int u, int v, Flow c) {
cap[u][v] += c;
cap[v][u] += c;
flow[v][u] += c;
g[u].push_back(v);
g[v].push_back(u);
}
Flow solve(int s, int t) {
Flow res = 0, aug = 1;
while (aug > 0) res += (aug = augment(s, t));
return res;
}
Flow augment(int s, int t) {
prev.assign(n, -1);
level.assign(n, inf);
level[s] = 0;
std::queue<std::pair<int, Flow>> q;
q.emplace(s, inf);
Flow aug = 0;
while (q.size()) {
int v;
Flow f;
std::tie(v, f) = q.front();
q.pop();
if (v == t) {
aug = f;
break;
}
for (const int &d : g[v]) {
if (level[d] <= level[v] + 1 || cap[v][d] - flow[v][d] == 0) continue;
level[d] = level[v] + 1;
prev[d] = v;
q.emplace(d, std::min(f, cap[v][d] - flow[v][d]));
}
}
if (aug == 0) return 0;
int c = t;
while (c != s) {
int p = prev[c];
flow[p][c] += aug;
flow[c][p] -= aug;
c = p;
}
return aug;
}
};