NAME="Author" CONTENT="Niwa Masahiro"> 最大流量問題(Dinic)
ホームに戻る
最大流量問題(Dinic)

// 計算量が早いのでDinicを使うのが無難。
// O(V^2*E)だがそれよりも速いらしい。
// スタートからゴールへの最大流量を求める。
// #define MAX_V 55 の数値を調整すること。
// MAX_V は最大ノード数
// ae(from,to,cost)で枝を追加する。
// maxFlowDinic(from,to)で最大量を流す。

// 流れた流量は全て流れ終わった後の逆辺の容量に等しい。
// iからjまでの流量を調べるのはE[i]のエッジのうちjに行くものを調べる。

#define MAX_V 55
#define INF 1000000000000000000LL

struct edge{long long to,reve;long long cap;};

vector<edge> E[MAX_V];
long long itr[MAX_V],lev[MAX_V];

void ae(long long x,long long y,long long cap){
  E[x].push_back((edge){y,(int)E[y].size(),cap});
  E[y].push_back((edge){x,(int)E[x].size()-1,0});
}

void bfs(long long cur){
  memset(lev,-1,sizeof(lev));
  queue<long long> q;
  lev[cur]=0;
  q.push(cur);
  while(q.size()){
    long long v=q.front(); q.pop();
    for(long long i = 0; i < E[v].size(); i++){
      edge &e = E[v][i];
      if(e.cap>0 && lev[e.to]<0){
        lev[e.to]=lev[v]+1, q.push(e.to);
      }
    }
  }
}

long long dfs(long long from,long long to,long long cf){
  if(from==to) return cf;
  for(long long &i = itr[from]; i < E[from].size(); i++){
    edge &e = E[from][i];
    if(e.cap>0 && lev[from]<lev[e.to]){
      long long f=dfs(e.to,to,min(cf,e.cap));
      if(f>0){
        e.cap-=f;
        E[e.to][e.reve].cap += f;
        return f;
      }
    }
  }
  return 0;
}

long long maxFlowDinic(long long from, long long to) {
  long long fl=0,tf;
  while(1) {
    bfs(from);
    if(lev[to]<0)return fl;
    memset(itr,0,sizeof(itr));
    while((tf=dfs(from,to,numeric_limits<int>::max()))>0)fl+=tf;
  }
}

int main(){
  ae(0,1,4);
  ae(1,2,5);
  ae(2,3,10);
  cout << maxFlowDinic(0,3) << endl;
  return 0;
}

inserted by FC2 system