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

前提

Dinic法を理解するには、先にFord-Fulkerson法を知っていると早い。

pione.hatenablog.com

Dinic法の基本的な動作はFord-Fulkerson法と同じで、残余グラフを構築して増加路の辺、逆辺の capacity を更新していき、更新できるパスがなくなるまでそれを繰り返している。

Dinic法ではこれを効率化するためにBFSとDFSを併用している。（DFSとBFSの実行順序は以下の参考1のフローチャートがわかりやすい。）

BFS

始点sから各ノードへの最短距離levelを求める。level配列は-1で初期化し、BFSは移動可能な辺（つまり level[v]<0 && capacity>0 である辺）のみを使って遷移し、level配列を更新していく。 level[t]==-1 であるなら、増加路が存在しないことになるのでその時点で更新を終了する。

DFS

次に、求めたlevelを活用しつつDFSを行う。 グラフに増加路が存在するとき、その増加路の頂点のどの隣り合う頂点間には、level[from]<level[to] && capacity>0 が成り立つはずなので、これを満たす頂点間のみの遷移を見ればよい。

ある1つの増加路の流量を求められたら、Ford-Fulkerson法と同じ要領で残余グラフの辺、逆辺の capacity を更新する。 この際、調べた辺を記録しておく。（以下の実装におけるitr配列）

再度DFSにより増加路を探す際、itr配列を使えば、既にその辺から先に増加路は無いと分かっている辺をスキップすることができるため効率化ができる。（ここがFord-Fulkerson法と比較したDinic法の優位な点だと思う。）

計算量: O(|V|^2|E|)（頂点数をV、辺数をEとする）

実際にはこの計算量よりも早い結果になることが多い。（参考2の記事を参照）

参考

参考1）

以下の記事のフローチャートはとても参考になる。

vartkw.hatenablog.com

参考2）

計算量に関する記事。

topcoder-g-hatena-ne-jp.jag-icpc.org

検証用問題

onlinejudge.u-aizu.ac.jp

実装

template <class T>
class Dinic {
private:
  const int INF = 1e9;
  vector<int> level, itr;

  struct Edge {
    int to, rev; T cap;
    Edge(int to, int rev, T cap) : to(to), rev(rev), cap(cap){};
  };

  vector<vector<Edge>> G;

  Edge &get_rev(Edge &edge) { return G[edge.to][edge.rev]; }

  void bfs(int s) {
    level.assign(G.size(), -1);
    level[s] = 0;
    queue<int> q;
    q.push(s);
    while (!q.empty()) {
      auto v = q.front();
      q.pop();
      for (auto &e : G[v]) {
        if (level[e.to] < 0 and e.cap > 0) {
          level[e.to] = level[v] + 1;
          q.push(e.to);
        }
      }
    }
  }

  T dfs(int v, int t, T flow) {
    if (v == t) return flow;
    for (int &i = itr[v]; i < G[v].size(); i++) {
      auto &edge = G[v][i];
      if (level[v] < level[edge.to] and edge.cap > 0) {
        auto f = dfs(edge.to, t, min(flow, edge.cap));
        if (f > 0) {
          edge.cap -= f;
          get_rev(edge).cap += f;
          return f;
        }
      }
    }
    return 0;
  }

public:
  Dinic(int n) { G.resize(n); }

  void add_edge(int from, int to, T cap) {
    G[from].push_back(Edge(to, (int)G[to].size(), cap));
    G[to].push_back(Edge(from, (int)G[from].size() - 1, 0));
  }

  T get_max_flow(int s, int t) {
    int n = G.size();
    T res = 0;
    while (true) {
      itr.assign(n, 0);
      bfs(s);
      if (level[t] < 0) break;
      while (true) {
        T flow = dfs(s, t, INF);
        if (flow > 0) res += flow;
        else break;
      }
    }
    return res;
  }
};