【C++】Dinic法の実装

Dinic法とは

グラフの最大流を求めるためのアルゴリズムです。やっていることはFord-Fulkerson法とまあまあ似ていますが、最短の増加パスに注目することで計算量を小さくすることを目指します。ちなみに、最大流とは

• グラフ$G=(e,v)$において、$s$から$t$に向かって最大でどれだけの量のフローを流せるかを求める

という問題のことです。
Dinic法は以下の手順で行います。

1. 距離が増加する向きの辺のみで構成されたグラフをbfsで取得する。
2. グラフにおける増加パスをdfsで求め、フローを流す。
3. 全ての増加パスにフローを流しおわったら1に戻り、これを増加パスが存在しなくなるまで繰り返す。

1は常に最短の増加パスを考える操作に相当しますが、最短の増加パスの長さはフローを流すにつれて真に増加していくため、違う残余グラフで同じ経路を巡るということはありません。

Dinic法の計算量

bfsでのグラフ取得は$O(|V|)$で行えます。増加パスを求めるdfsですが、距離が増加する向きの辺のみで構成することによって同じ辺を調べるという操作がなくなるため、各ステップに対して$O(|E|)$、つまり全体として$O(|V||E|)$で行えます。
結局、1と2を合わせた計算量は$O(|V||E|)$となり、これを最大で最短パスの長さの種類分、つまり$|V|-1$回繰り返すので、Dinic法の計算量は$O(|V|^2|E|)$となります。
しかし個々の最悪ケースは互いに両立しないため、実際にはここまでの計算量になることはなく、$O(|V|^2|E|)$で危なそうでも通ってしまうことが多いみたいです。

Dinic法の実装

用いる変数は以下の通りです。

struct edge{int to,cap,rev;}; //辺を記述 to:行き先,cap:容量,rev:逆辺の位置
int level[MAX_V]; //sからの距離
int iter[MAX_V]; //どこまで調べ終わったか
vector<edge> G[MAX_V];//辺の隣接リスト表現

辺を追加する操作は以下の通りです。Ford-Fulkerson法と同様に、逆辺も追加する必要があることに注意してください。vectorの最後尾を逆辺の位置として管理します。

void add_node(int from, int to, int cap){
    edge e = {to,cap,G[to].size()}; //辺
    G[from].push_back(e);
    e = {from, cap, G[from].size()-1}; //逆辺
    G[to].push_back(e);
}

bfsでグラフを取得する操作は以下の通りです。本当にただのbfsです。

void bfs(int s){
  memset(level,-1,sizeof(level));
  queue<int> Q;
  Q.push(s); level[s]=0;
  while(!Q.empty()){
    int v=Q.front(); Q.pop();
    for(int i=0;i<G[v].size();i++){
      edge& e = G[v][i];
      if(e.cap >0 && level[e.to]<0){ 
        level[e.to] = level[v]+1;
        Q.push(e.to);
      }
    }
  }
}

dfsで1つの増加パスを取得する操作は以下の通りです。

int dfs(int v, int t, int f){
  if(v==t) return f; //到達した
  for(int& i=iter[v];i<G[v].size();i++){ //呼び出しながらiterを更新
    edge& e=G[v][i];
    if(e.cap>0 && level[v]<level[e.to]){ //距離が増加する向きのみ
      int d = dfs(e.to, t, min(f,e.cap));
      if(d>0){
        e.cap -= d;
        G[e.to][e.rev].cap += d;
        return d;
      }
    }
  }
  return 0; //到達できない
}

最大流を求める操作は以下の通りです。whileの二重となっていてギョっとしますが、特に心配はいりません。どうしても心配なら繰り返し回数が考えうる最大流量を超過したときに中断するような処理を追加すればよいでしょう。

int max_flow(int s, int t){
  int flow=0;
  while(true){
    bfs(s);
    if(level[t]<0) return flow; //パスが存在しなくなった
    memset(iter,0,sizeof(iter));
    int f;
    while(f=dfs(s,t,infi) >0){//増加パスが存在するまで
      flow += f;
    }
  }
}