NAME="Author" CONTENT="Niwa Masahiro">
最大流量問題(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; }