Ford-Fulkersonのアルゴリズム

最大フローを求めるアルゴリズム

逆向きの辺を張るのがミソ。これが分かれば半分は理解している気がする

逆辺と普通の辺は区別されないよ（重要）

おきもち

残余ネットワーク上で1以上の増加道をDFSで求めて流す、を繰り返していく

増加道がたくさんあるときでも一番最初に見つけたやつに流す

最悪計算量は、最大の流量をFとしたとき、流量1の増加道を見つけて流す、流量1、流量1…のパターンだと流す作業が最大でF回発生することになって、それぞれのDFSはO(|E|)なので(辺の本数を|E|としています)、O(F|E|)となる。実際の体感はもう少し早く終わるらしいです。知らんけど。

実装

わかりよい…

下のコードを貼ると通ります

code:Ford-Fulkerson.cpp

using namespace std;

typedef long long int ll;

ll MOD = 1000000007;

ll INFL = 1ll << 60;

ll INF = 1 << 28;

struct edge {

int to, cap, rev;

};

vector<bool> used;

vector<vector<edge>> G;

// 辺を追加する

void add_edge(int from, int to, int cap) {

}

// とりあえず増加パスを探す。nowからtに向かいたい。

int flow_dfs(int now, int t, int mincap) { // mincap...現在までの最小容量

if (now == t) return mincap;

int d = flow_dfs(e.to, t, min(mincap, e.cap));

if (d > 0) { // tに行ってきたなら、return mincapでdに1以上が格納されている

e.cap -= d;

return d;

}

}

}

return 0; // どこにも増加パスが存在しなかった...

}

// sからtへの最大流を求める

int max_flow(int s, int t) {

int flow = 0;

while (true) { // 新たな増加パスを探し続ける

used.assign(used.size(), false);

int f = flow_dfs(s, t, INF);

if (f == 0) return flow; // 増加パスが見つからなかった

flow += f;

}

}

// ====================================================================

int main() {

int V, E;

cin >> V >> E;

G.assign(V, vector<edge>());

used.assign(V, false);

for (int i = 0; i < E; i++) { // 残余ネットワークを構築

int u, v, c;

cin >> u >> v >> c;

add_edge(u, v, c);

}

cout << max_flow(0, V - 1) << endl;

}