9 // Verified by 9 // Verified by 10 // - SRM 399 Div1 LV3 10 // - SRM 399 Div1 LV3 11 // - PKU 1459 11 // - PKU 1459 12 // - CodeCraft 09 CUTS 12 // - CodeCraft 09 CUTS 13 // - SRM 465 Div1 LV2 13 // - SRM 465 Div1 LV2 14 //------------------------------------------------------------- 14 //------------------------------------------------------------- 15 15 16 static const int NV = 512; | 16 template<typename T> 17 typedef int flow; | 17 class IdGen 18 typedef int vert; < 19 typedef vert edge; < 20 typedef vector<edge> edges; < 21 typedef vector<edges> graph; < 22 typedef flow flow_graph[NV][NV]; < 23 < 24 flow dinic_dfs( graph& G, flow_graph F, vert v, vert D, < 25 int LV[], flow flow_in, int blocked[] ) < 26 { 18 { 27 flow flow_out = 0; | 19 map<T, int> v2id_; 28 for(int i=0; i!=G[v].size(); ++i) { | 20 vector<T> id2v_; 29 int u = G[v][i]; | 21 public: 30 if( LV[v]+1==LV[u] && F[v][u] ) { | 22 int v2id(const T& v) { 31 flow f = min(flow_in-flow_out, F[v][u]); | 23 if( !v2id_.count(v) ) { v2id_[v] = size(); id2v_.push_back(v); } 32 if( u==D || !blocked[u] && (f=dinic_dfs(G,F,u,D,LV,f,blo | 24 return v2id_[v]; 33 F[v][u] -= f; < 34 F[u][v] += f; < 35 flow_out += f; < 36 if( flow_in == flow_out ) return flow_out; < 37 } < 38 } < 39 } 25 } 40 blocked[v] = (flow_out==0); | 26 const T& id2v(int i) const { return id2v_[i]; } 41 return flow_out; | 27 int size() const { return id2v_.size(); } 42 } | 28 }; 43 29 44 flow maxFlow( graph& G, flow_graph F, vert S, vert D ) | 30 template<typename Vert, typename Flow, int NV=512> > 31 class MaxFlow 45 { 32 { > 33 IdGen<Vert> idgen; > 34 vector<int> G[NV]; > 35 Flow F[NV][NV]; > 36 > 37 public: > 38 void addEdge( Vert s_, Vert t_, Flow f ) > 39 { > 40 const int s = idgen.v2id(s_), t = idgen.v2id(t_); > 41 G[s].push_back(t); > 42 G[t].push_back(s); > 43 F[s][t] = f; > 44 F[t][s] = 0; > 45 } > 46 > 47 Flow calc( Vert s_, Vert t_ ) > 48 { > 49 const int S = idgen.v2id(s_), D = idgen.v2id(t_); 46 for( flow total=0 ;; ) { | 50 for( Flow total=0 ;; ) { > 51 // Do BFS and compute the level for each node. 47 int LV[NV] = {0}; | 52 int LV[NV] = {0}; 48 vector<int> Q(1, S); | 53 vector<int> Q(1, S); 49 for(int lv=1; !Q.empty(); ++lv) { | 54 for(int lv=1; !Q.empty(); ++lv) { 50 vector<int> Q2; | 55 vector<int> Q2; 51 for(int i=0; i!=Q.size(); ++i) { | 56 for(size_t i=0; i!=Q.size(); ++i) { 52 edges& ne = G[Q[i]]; | 57 const vector<int>& ne = G[Q[i]]; 53 for(int j=0; j!=ne.size(); ++j) | 58 for(size_t j=0; j!=ne.size(); ++j) 54 if( F[Q[i]][ne[j]] && !LV[ne[j]] && ne[j | 59 if( F[Q[i]][ne[j]] && !LV[ne[j]] 55 LV[ne[j]]=lv, Q2.push_back(ne[j] | 60 LV[ne[j]]=lv, Q2.push_ba > 61 } > 62 Q.swap(Q2); 56 } 63 } 57 Q.swap(Q2); < 58 } | 64 > 65 // Destination is now unreachable. Done. > 66 if( !LV[D] ) > 67 return total; 59 68 60 if( !LV[D] ) | 69 // Iterating DFS. 61 return total; | 70 bool blocked[NV] = {}; > 71 total += dinic_dfs( S, D, LV, 0x7fffffff, blocked ); > 72 } > 73 } 62 74 63 int blocked[NV] = {}; | 75 private: 64 total += dinic_dfs( G, F, S, D, LV, 0x7fffffff, blocked ); | 76 Flow dinic_dfs( int v, int D, int LV[], Flow flow_in, bool blocked[] ) > 77 { > 78 Flow flow_out = 0; > 79 for(size_t i=0; i!=G[v].size(); ++i) { > 80 int u = G[v][i]; > 81 if( LV[v]+1==LV[u] && F[v][u] ) { > 82 Flow f = min(flow_in-flow_out, F[v][u]); > 83 if( u==D || !blocked[u] && (f=dinic_dfs(u,D,LV,f > 84 F[v][u] -= f; > 85 F[u][v] += f; > 86 flow_out += f; > 87 if( flow_in == flow_out ) return flow_ou > 88 } > 89 } > 90 } > 91 blocked[v] = (flow_out==0); > 92 return flow_out; 65 } 93 } 66 } | 94 };