ホーム > libalgo

最大流 (Edmonds-Kerp)

概要

Edmonds-Kerp のアルゴリズムはグラフの最大流を求める.FF との違いは増加道の選択が辺の数の意味での最短経路を選ぶという点だけ.

計算量

この実装では隣接行列を生成しているので $O(VE^2 + V^2)$.

使い方

using Flow = intEdge 構造体に Flow cap というメンバを追加する

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

実装

struct edmonds_kerp {
    int n;
    std::vector<int> prev, level;
    std::vector<std::vector<Flow>> cap, flow;
    std::vector<std::vector<int>> g;
    Flow inf;
    edmonds_kerp(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) {}
    edmonds_kerp(const Graph &graph) {
        *this = edmonds_kerp(graph.size());
        rep(i, n) 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) {
        Flow res = 0, aug = 1;
        while (aug > 0) res += (aug = augment(s, t));
        return res;
    }
    Flow augment(int s, int t) {
        prev.assign(n, -1);
        level.assign(n, inf);
        level[s] = 0;
        std::queue<std::pair<int, Flow>> q;
        q.emplace(s, inf);
        Flow aug = 0;
        while (q.size()) {
            int v;
            Flow f;
            std::tie(v, f) = q.front();
            q.pop();
            if (v == t) {
                aug = f;
                break;
            }
            for (const int &d : g[v]) {
                if (level[d] <= level[v] + 1 || cap[v][d] - flow[v][d] == 0) continue;
                level[d] = level[v] + 1;
                prev[d] = v;
                q.emplace(d, std::min(f, cap[v][d] - flow[v][d]));
            }
        }
        if (aug == 0) return 0;
        int c = t;
        while (c != s) {
            int p = prev[c];
            flow[p][c] += aug;
            flow[c][p] -= aug;
            c = p;
        }
        return aug;
    }
};

検証

AOJ GLP6A (Submission)