【最大流・最小カット】FordFulkerson法を実装してみた【C++】

Ford-Fulkerson法

超ざっくりいうと、フローネットワークの最大フローを求めることができるアルゴリズムです。
この最大フローは最小カットと等しいという定理があるため、最大フローおよび最小カットを求めるアルゴリズムでもあります。
二部マッチングも最大流の問題に帰着できることがあり、そこでもフォードファルカーソン法は用いられます。

計算量

頂点数をM、最大流量をFとおきます。
頂点sからtへのDFSによる経路の検出に O(M) かかります。
また、一回のフローで総流量は1以上であるので、経路の探索を行う回数自体は高々 O(F) です。
よって、O(FM) となります。

典型的な問題を解いてみる

鉄則本a68 をフォードファルカーソン法で解いてみました。
実装にあたって、FordFulkersonというclassを作り、そのメソッドに辺の生成と残余ネットワークの更新を行う機能を付けました。
実際に使うときはffというインスタンスを生成した場合、

 ff.init(n);           //グラフの初期化
 ff.add_edge(a, b, c); //from, to, costで辺を生成
 ff.maxFlow(0, n-1)    //答えを取得

の三つの関数だけで済みます。

それではコードを以下に示します。

C＋＋での実装例

FordFulkerson.cpp

/*FORDFULKERSON*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define rep(i, a, b) for (int i = a; i < b; i++)
#define INF (1e9 + 1)

//辺の構造体
struct Edge {
    //rev: toから行ける頂点のうち、toから見てfromが何番目に位置するか
    //G[from].size() == rev  
    int rev, from, to, cap;
};

//フォードファルカーソン法
class FordFulkerson {
public:
    vector<vector<Edge>> G;
    vector<bool> visited;
    // 頂点数 n の残余グラフを用意
    int size = 0;
    void init(int n) {
        G.resize(n);
        visited.resize(n);
        size = n;
    }
    /*
        頂点 u -> v について 上限 cost の辺を追加
        コスト0の逆辺も張る
    */ 
    void add_edge(int u, int v, int cost) {
        int u_vID = G[u].size(); // 現時点での G[u] の要素数 = uからみたvのindex
        int v_uID = G[v].size(); // 現時点での G[v] の要素数 = vからみたuのindex
        G[u].emplace_back(Edge{v_uID, u, v, cost}); //<u,v>の逆辺<v,u>はG[u][v_uID]
        G[v].emplace_back(Edge{u_vID, v, u, 0}); //逆辺は追加時はコスト0!!
    }
    /*  
        深さ優先探索（F はスタートした頂点からposに到達する過程での
 　　　　"残余グラフの辺の容量" の最小値）
        goalまでの往路は頂点を記録しながらs->tまでに共通して流せる容量
　　　　　　　　　　　　　　　　　　　　　　 = s->tまでの容量の最小値を取得
        復路はs->tまでの容量の最小値を使って残余ネットワークのコストを更新
        返り値: 流したフローの量
    */
    int dfs(int pos, int goal, int F) {
        if (pos == goal) return F; //ゴールに到着したら流す
        visited[pos] = true; //訪れた頂点を記録
    
        // G[pos]に隣接する頂点を探索
        for(auto &e : G[pos]){
            //容量0の辺や訪問済みの頂点は無視
            if (e.cap == 0 or visited[e.to]) continue;
            // 再帰で目的地までのパスを探す
            int flow = dfs(e.to, goal, min(F, e.cap));
            // 残余ネットワークの更新
            // フローを流せる場合、残余グラフの容量をflowだけ増減させる
            if (flow > 0) {
                e.cap -= flow;              //u->vの辺を減少
                G[e.to][e.rev].cap += flow; //v->uの辺を増加
                return flow;
            }
        }
        return 0;
    }
 
    // 頂点sから頂点tまでの最大フローの総流量を返す
    int maxFlow(int s, int t) {
        int totalFlow = 0;
        while (true) {
　　　　　　//s->tに探索する前に記録した頂点をリセット
            visited.assign(size, false);
            int F = dfs(s, t, INF); //s->tへの流量を取得
            //フローを流せなくなったら終了
            if (F == 0) break;
            totalFlow += F;
        }
        return totalFlow;
    }
};

//グローバル変数で管理
int n, m;
int a,b,c;

//FordFulkersonのインスタンスff
FordFulkerson ff;
 
int main() {
    // 入力
    cin >> n >> m;
    //グラフの作成
    ff.init(n);
    rep(i,0,m){
        cin >> a >> b >> c;
        a--; b--;
        ff.add_edge(a, b, c); //from, to, costで辺を生成
    }
    //頂点0->n-1までの最大流の出力
    cout << ff.maxFlow(0, n-1) << endl;
    return 0;
}

このようになります。

解けました！