AOJ GRL_6_A : Maximum Flow
AOJ GRL_6_A : Maximum Flow に関連する、ネットワークフローの最大フロー最小カット定理についてのメモを残します。
参考
- 「プログラミングコンテストチャレンジブック」(蟻本)
面白い
「ネットワークフロー」とは何なのか、については、
この記事で説明されていて、面白いです。
ネットワークフローは、グラフ理論で登場するグラフの一種ですが、そもそも「グラフ」とは何なのか、については、
この記事で簡単に説明されています。
最大流問題
から へ単位時間当たり最大でどれだけのデータを送れるか (最大流) を求める問題。このような問題を最大流問題という。
最大流を求める方法として Ford-Fulkerson のアルゴリズムが知られている。
- 残余グラフにおいて、 から へのパスを見つける
- そのようなパスが無ければ終了。パスが存在したら、そのパスに流せるだけ流し、1. に戻る
下図は、 → 1 → 2 → のパスに 5 流したときの残余グラフで、辺に添えられた数は、辺の残り容量を表す。
このあと、 → 1 → 3 → のパスに 5 流し、さらに、 → 2 → 1 → 3 → のパスに 1 流すと、残余グラフは下図のようになる。
から へのパスは存在しないので、これで終了。最大流は 11 Mbps であることがわかった。
最大フロー最小カット定理
Ford-Fulkerson のアルゴリズムによって最大流が正しく求められることを示す。
任意の フロー と任意の カット (、、、) について、
( から出る辺の流量) ( から出る辺の流量)
ここで、 から出る辺の流量、 から出る辺の流量はともに非負であり、辺の流量が辺の容量を超えることはないので、
( から出る辺の容量) ( の容量) ... (1)
となることがわかる。
次に、Ford-Fulkerson のアルゴリズムによって得られた フロー に注目する。
残余グラフにおいて、 から到達可能な頂点集合を 、集合 とすると、 は カットである。
また、 から へ向かう辺は存在せず、もとのグラフにおいて、
( から出る辺の流量) ( から出る辺の容量) ( の容量)、
( から出る辺の流量) 0
下図は、もとのグラフで、辺に添えられた数は、辺の流量を表す。また、赤色の辺は、カット に属する。
したがって、
( から出る辺の流量) ( から出る辺の流量) ( の容量)
これと (1) から、Ford-Fulkerson のアルゴリズムによって得られたフロー は最大流であり、 は最小カットであることがわかる。
実装
#include <bits/stdc++.h> using namespace std; const int INF = 1000000007; struct Edge { int to, cap, rev; }; // 行き先, 容量, 逆辺(index) vector<vector<Edge>> G; vector<bool> used; // from から to へ向かう辺 (容量 cap) と逆辺をグラフに追加 void addEdge(int from, int to, int cap) { Edge e1 = { to, cap, (int)G.at(to).size() }; G.at(from).push_back(e1); Edge e2 = { from, 0, (int)G.at(from).size() - 1 }; G.at(to).push_back(e2); } // 増加パスを 1 つ見つけて、流量を返す int dfs(int v, int t, int f) { if (v == t) return f; // ゴールに到着 used.at(v) = true; // 訪問済み for (auto &e : G.at(v)) { // まだ容量の残っている隣接頂点に流したい if (!used.at(e.to) && e.cap > 0) { int d = dfs(e.to, t, min(f, e.cap)); if (d > 0) { e.cap -= d; G.at(e.to).at(e.rev).cap += d; // 逆辺 return d; } } } return 0; // 増加パスが存在しない } // 始点 s、終点 t の最大流を返す int maxFlow(int s, int t) { int flow = 0; while (true) { fill(used.begin(), used.end(), false); int f = dfs(s, t, INF); // 増加パスを 1 つ見つける if (f == 0) return flow; // 増加パスが存在しない flow += f; } } int main() { int V, E; cin >> V >> E; G.resize(V); used.resize(V); for (int i = 0; i < E; i++) { int u, v, c; cin >> u >> v >> c; addEdge(u, v, c); } cout << maxFlow(0, V-1) << endl; }