最大流問題とFord-Fulkerson法に関する個人的なメモ

前提

最大流問題とは、辺に capacity を持つグラフが与えられて、始点から目いっぱい水を流した時に終点に流せる最大量を求める問題。

グラフの最大流は、そのグラフのS-T最小カットに対応する。

計算量: O(|flow||E|) （最大フローをflow、辺数をEとする）

|E| の部分は一度のDFSを意味し、一度のDFSで少なくとも1以上流量が改善され、流量の改善は高々そのグラフの最大流までしかないことから計算量に最大流 flow が登場する。 実際には1ずつの更新が flow 回行われるということはほとんどないので |flow| より計算量は良くなる。

Ford-Fulkerson法では、与えられたグラフに対して以下の様な規則で逆辺をも持つ新しいグラフを構築し、このグラフに対して貪欲的に値を更新していくことで解を求めている。（この逆辺を張ったグラフを残余グラフと呼ぶ。）残余グラフではなく、元のグラフに対して貪欲法で解を求めようとすると正しい解が求まらないことは、以下に載せた 参考2 のスライドに図解がある。

与えられた元のグラフのある辺に対して、同じ方向の辺はその辺に流すことができる残容量、逆方向の辺は既にその辺に流した流量、として双方向に辺を張ったグラフを構築する。すると、逆辺の値を減らすことは今流している流量を減らすこと、元の辺の値を減らすことは残容量を減らす（つまり辺に追加で流す）ことに対応する。場合によっては、ある辺の流量を減らす（逆辺の値を減らす）ことで全体の流量が改善する場合があり（参考1 P23 参照）、そのため流量を増やす、減らすの双方向の操作ができる残余グラフである必要がある。

ここで、同じ辺が流量を増やされたり減らされたり何度も更新される可能性があるため、無限ループしないかという不安がある。 しかし、更新を続けることでいずれS-T最小カットが定まる（つまりS-Tの増加路がなくなる）ため、その時点で更新が終了するため心配はない。

二部グラフの最大マッチング

最大流の有名な応用例として、二部グラフの最大マッチングを求めるものがある。

元の二部グラフに最大流を流すための source と sink 用の2つの頂点を追加することを考える。

二部グラフの頂点部分集合、X、Yのどちらかに対して source からの辺を張り、もう片方から sink への辺を張る。すると s-t最大流が求める最大マッチングの値になる。（参考4に最大流が二部グラフのマッチングになることの図解がある）

参考

参考1）残余グラフの更新の様子が図解してあり非常にわかりやすいです。

http://hos.ac/slides/20150319_flow.pdf

参考2）P.13 に間違った貪欲法では求まらない例の図が参考になります。

グラフネットワーク〜フロー&カット〜 from HCPC: 北海道大学競技プログラミングサークル

www.slideshare.net

参考3）実装を参考にさせていただきました。

algo-logic.info

参考4）二部グラフの最大マッチングについて

qiita.com

検証用問題

最大流

onlinejudge.u-aizu.ac.jp

二部グラフの最大マッチング

onlinejudge.u-aizu.ac.jp

実装

template <class T>
class FordFulkerson {
private:
  const T INF = 1e9;
  
  struct Edge {
    int to, from, rev; T cap;
    Edge(int from, int to, int rev, T cap) : to(to), from(from), rev(rev), cap(cap) {}
  };
  
  vector<vector<Edge>> G;
  
  Edge &get_rev(Edge &edge) { return G[edge.to][edge.rev]; }
  
  vector<bool> used;
  
  T dfs(int v, int t, T flow) {
    if (v == t) return flow;
    used[v] = true;
    for (auto &e : G[v]) {
      if (used[e.to] or e.cap <= 0) continue;
      T d = dfs(e.to, t, min(flow, e.cap));
      if (d > 0) {
        e.cap -= d;
        get_rev(e).cap += d;
        return d;
      }
    }
    return 0;
  }

public:
  FordFulkerson(int n) { G.resize(n); }
  
  void add_edge(int from, int to, T cap) {
    G[from].push_back(Edge(from, to, (int)G[to].size(), cap));
    G[to].push_back(Edge(to, from, (int)G[from].size() - 1, 0));
  }
  
  T get_max_flow(int s, int t) {
    int n = G.size();
    T res = 0;
    while (true) {
      used.assign(n, false);
      T flow = dfs(s, t, INF);
      if (flow > 0) {
        res += flow;
      } else {
        return res;
      }
    }
    return 0;
  }
};