三浦ノート

自分の経験したことを検索可能にしていくブログ.誰かの役に立ってくれれば嬉しいです.

Ford-Fulkerson法の実装解説

グラフの最大流問題を解くアルゴリズムのFord-Fulkerson法のC++実装例が

プログラミングコンテストチャレンジブック [第2版] ~問題解決のアルゴリズム活用力とコーディングテクニックを鍛える~

(蟻本)p190にあります.アルゴリズム自体は本文にある説明からわかった気がするのですが,プログラム実装については自分にとってちょっと難しかったので解読して分かったことをまとめます.とくに残余グラフの持ち方が理解に手こずりましたが,すこし分かってくるととても巧い実装だなと思いました.強い人が書いたプログラムは非常に勉強になります.

以下のコードは Aizu Online Judge でACとなるように書き直したコードです.適宜コメントを追加しました.

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int64_t i=(a); i<(b); ++i) // a ≦ i < b 
#define INF 1000000000

// 辺の(行先,容量,逆辺が保存されているG[to]での番地).
struct edge {int to, cap, rev;};

vector<bool> used; //dfsですでに調べた頂点はtrue.
vector<vector<edge>> G; //有向グラフとその残余グラフ.

// from から to への容量 cap の辺とその逆辺をグラフ G に追加する.
// 辺 e の逆辺は G[e.to] の rev 番目に追加される.
// G[e.to][e.rev] = 辺 e の逆辺 .
void add_edge(int from, int to , int cap){
    G[from].push_back(edge{to, cap, (int)G[to].size()});
    G[to].push_back(edge{from, 0, (int)G[from].size() - 1});
}

//v から t へのパスを DFS で探し,そのパスに流せる最大流量を返す.
// mincap = 通った辺の中の最少容量
int flow_dfs(int v, int t, int mincap){
    if (v == t) return mincap;
    used[v] = true;
    for (edge &e:G[v])
        if(!used[e.to] && e.cap > 0){
            int d = flow_dfs(e.to, t, min(mincap, e.cap));
            if (d > 0){
                e.cap -= d;
                G[e.to][e.rev].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() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    int V, E; cin >> V >> E;
    G.assign(V, vector<edge>());
    used.assign(V, false);
    rep(i, 0, E){
        int u, v, c; cin >> u >> v >> c;
        add_edge(u, v, c); 
        //もし無効グラフなら add_edge(v, u, c); もする.
    }

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

}