Spaghetti Source logo

最大流 (Edmonds-Karp)

目的

Edmond-Karp は最短路反復によって最大流問題を解くアルゴリズムである.

始点から終点までの(辺の本数の意味での)最短路を求め,そこにフローを流す.到達不能になるまでこれを繰り返す.整数フローの場合は必ず停止するが,実数フローの場合止まらないケースが存在する.

最大流最小カット定理によって,最大流が求まったとき同時に最小カットも求まっている.

プログラミングコンテストで出るような問題であればこれでほとんどの場合十分であるが,速度が問題になる場合は一段高速なアルゴリズム(Dinic,Goldberg-Tarjan)を検討することになる.

計算量

O(E^2 V).以下の実装では内部で隣接行列を生成するため,O(V^2) の追加コストがかかっている.

ソースコード

#define RESIDUE(s,t) (capacity[s][t]-flow[s][t])
Weight maximumFlow(const Graph &g, int s, int t) {
  int n = g.size();
  Matrix flow(n, Array(n)), capacity(n, Array(n));
  REP(u,n) FOR(e,g[u]) capacity[e->src][e->dst] += e->weight;

  Weight total = 0;
  while (1) {
    queue<int> Q; Q.push(s);
    vector<int> prev(n, -1); prev[s] = s;
    while (!Q.empty() && prev[t] < 0) {
      int u = Q.front(); Q.pop();
      FOR(e,g[u]) if (prev[e->dst] < 0 && RESIDUE(u, e->dst) > 0) {
        prev[e->dst] = u;
        Q.push(e->dst);
      }
    }
    if (prev[t] < 0) return total; // prev[x] == -1 <=> t-side
    Weight inc = INF;
    for (int j = t; prev[j] != j; j = prev[j])
      inc = min(inc, RESIDUE(prev[j], j));
    for (int j = t; prev[j] != j; j = prev[j])
      flow[prev[j]][j] += inc, flow[j][prev[j]] -= inc;
    total += inc;
  }
}

Verified

前原 貴憲(maehara@prefield.com).

Last Modified: 2007.11.12 22:01:05.