最大流 (Ford-Fulkerson)

概要

Ford-Fulkerson のアルゴリズムはグラフの最大流を求める．始点から終点への経路があって，経路上の各辺に容量の空きがあるとき，その経路を使って流れを作ることができる．これを経路が見つかるたびにくりかえす．容量に空きがある経路を増加道 (augmenting path) と呼ぶ．

計算量

この実装では隣接行列を生成しているので $O(fE + V^2)$．ただし $f$ は最大流の流量．容量が整数以外の場合は無限ループに陥るケースが存在する．

使い方

using Flow = inf; し Edge 構造体に Flow cap というメンバを追加する

ford_fulkerson ff(g): グラフ g を組み込む
ford_fulkerson ff(N): 大きさ N のグラフを作る
ff.addEdge(u,v,c): u から v へ容量 c の辺を追加する
ff.solve(s,t): s から t への最大流を求める
ff.flow[u][v]: 辺 (u, v) の流量 (solve の実行後にのみ有効)

実装

struct ford_fulkerson {
    using Matrix = std::vector<std::vector<Flow>>;
    int n, t;
    std::vector<int> vis;
    std::vector<std::vector<Flow>> cap, flow;
    std::vector<std::vector<int>> g;
    const Flow INF;
    ford_fulkerson(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) {}
    ford_fulkerson(const Graph &graph) : ford_fulkerson(graph.size()) {
        for (int i = 0; i < n; ++i)
            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) {
        this->t = t;
        Flow res = 0, aug = 1;
        while (aug > 0) {
            vis.assign(n, false);
            res += (aug = augment(s, INF));
        }
        return res;
    }
    Flow augment(const int &v, const Flow &lim) {
        vis[v] = true;
        if (v == t) return lim;
        for (const int &d : g[v]) {
            if (vis[d] || flow[v][d] == cap[v][d]) continue;
            Flow aug = augment(d, std::min(lim, cap[v][d] - flow[v][d]));
            flow[v][d] += aug;
            flow[d][v] -= aug;
            if (aug > 0) return aug;
        }
        return 0;
    }
};

検証

AOJ GLP6A