2 //------------------------------------------------------------- 2 //------------------------------------------------------------- 3 // Dinic's Algorithm 3 // Dinic's Algorithm 4 // O(V E) 4 // O(V E) 5 // 5 // 6 // G : bidirectional (G[i].has(j) <==> G[j].has(i)) 6 // G : bidirectional (G[i].has(j) <==> G[j].has(i)) 7 // F : flow-capacity F[i][j] = Capacity, F[j][i] = 0 7 // F : flow-capacity F[i][j] = Capacity, F[j][i] = 0 8 // 8 // 9 // Verified by | 9 // Old versoin 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 // - SRM 543 Div1 LV3 14 // - SRM 543 Div1 LV3 15 //------------------------------------------------------------- 15 //------------------------------------------------------------- 16 16 ................................................................................................................................................................................ 24 if( !v2id_.count(v) ) { v2id_[v] = size(); id2v_.push_back(v); } 24 if( !v2id_.count(v) ) { v2id_[v] = size(); id2v_.push_back(v); } 25 return v2id_[v]; 25 return v2id_[v]; 26 } 26 } 27 const T& id2v(int i) const { return id2v_[i]; } 27 const T& id2v(int i) const { return id2v_[i]; } 28 int size() const { return id2v_.size(); } 28 int size() const { return id2v_.size(); } 29 }; 29 }; 30 30 31 template<typename Vert, typename Flow, int NV=2048> | 31 template<typename Vert, typename Flow, int NV=50*50*8+2> 32 class MaxFlow 32 class MaxFlow 33 { 33 { > 34 typedef int Edge; > 35 > 36 vector<int> G[NV]; > 37 vector<Flow> F; > 38 34 IdGen<Vert> idgen; 39 IdGen<Vert> idgen; > 40 map<pair<int,int>, Edge> edge_id; 35 vector<int> G[NV]; | 41 vector<int> Edge_to; 36 Flow F[NV][NV]; < > 42 vector<Edge> Edge_rev; 37 43 38 public: 44 public: 39 void addEdge( Vert s_, Vert t_, Flow f ) | 45 void add( Vert s_, Vert t_, Flow f ) 40 { 46 { 41 const int s = idgen.v2id(s_), t = idgen.v2id(t_); 47 const int s = idgen.v2id(s_), t = idgen.v2id(t_); > 48 if(!edge_id.count(make_pair(s,t))) { > 49 const int e = int(edge_id.size()); > 50 edge_id[make_pair(s,t)] = e; > 51 edge_id[make_pair(t,s)] = e+1; 42 G[s].push_back(t); | 52 G[s].push_back(e); 43 G[t].push_back(s); | 53 G[t].push_back(e+1); 44 F[s][t] = f; < 45 F[t][s] = 0; < > 54 F.push_back(0); > 55 F.push_back(0); > 56 Edge_rev.push_back(e+1); > 57 Edge_rev.push_back(e); > 58 Edge_to.push_back(t); > 59 Edge_to.push_back(s); > 60 } > 61 const Edge e = edge_id[make_pair(s,t)]; > 62 F[e] = min(F[e]+f, INF); 46 } 63 } 47 64 48 Flow calc( Vert s_, Vert t_ ) 65 Flow calc( Vert s_, Vert t_ ) 49 { 66 { 50 const int S = idgen.v2id(s_), D = idgen.v2id(t_); 67 const int S = idgen.v2id(s_), D = idgen.v2id(t_); 51 for( Flow total=0 ;; ) { 68 for( Flow total=0 ;; ) { 52 // Do BFS and compute the level for each node. 69 // Do BFS and compute the level for each node. 53 int LV[NV] = {0}; 70 int LV[NV] = {0}; 54 vector<int> Q(1, S); 71 vector<int> Q(1, S); 55 for(int lv=1; !Q.empty(); ++lv) { 72 for(int lv=1; !Q.empty(); ++lv) { 56 vector<int> Q2; 73 vector<int> Q2; 57 for(size_t i=0; i!=Q.size(); ++i) { 74 for(size_t i=0; i!=Q.size(); ++i) { 58 const vector<int>& ne = G[Q[i]]; | 75 const vector<Edge>& ne = G[Q[i]]; 59 for(size_t j=0; j!=ne.size(); ++j) | 76 for(size_t j=0; j!=ne.size(); ++j) { 60 if( F[Q[i]][ne[j]] && !LV[ne[j]] | 77 Edge e = ne[j]; > 78 int t = Edge_to[e]; > 79 if( F[e] && !LV[t] && t!=S ) 61 LV[ne[j]]=lv, Q2.push_ba | 80 LV[t]=lv, Q2.push_back(t > 81 } 62 } 82 } 63 Q.swap(Q2); 83 Q.swap(Q2); 64 } 84 } 65 85 66 // Destination is now unreachable. Done. 86 // Destination is now unreachable. Done. 67 if( !LV[D] ) 87 if( !LV[D] ) 68 return total; 88 return total; 69 89 70 // Iterating DFS. 90 // Iterating DFS. 71 bool blocked[NV] = {}; 91 bool blocked[NV] = {}; 72 total += dinic_dfs( S, D, LV, 0x7fffffff, blocked ); | 92 total += dinic_dfs( S, D, LV, INF, blocked ); 73 } 93 } 74 } 94 } 75 95 76 private: 96 private: 77 Flow dinic_dfs( int v, int D, int LV[], Flow flow_in, bool blocked[] ) 97 Flow dinic_dfs( int v, int D, int LV[], Flow flow_in, bool blocked[] ) 78 { 98 { 79 Flow flow_out = 0; 99 Flow flow_out = 0; 80 for(size_t i=0; i!=G[v].size(); ++i) { 100 for(size_t i=0; i!=G[v].size(); ++i) { 81 int u = G[v][i]; | 101 Edge e = G[v][i]; > 102 int u = Edge_to[e]; 82 if( LV[v]+1==LV[u] && F[v][u] ) { | 103 if( LV[v]+1==LV[u] && F[e] ) { 83 Flow f = min(flow_in-flow_out, F[v][u]); | 104 Flow f = min(flow_in-flow_out, F[e]); 84 if( u==D || !blocked[u] && (f=dinic_dfs(u,D,LV,f 105 if( u==D || !blocked[u] && (f=dinic_dfs(u,D,LV,f 85 F[v][u] -= f; | 106 F[e] -= f; 86 F[u][v] += f; | 107 F[Edge_rev[e]] += f; 87 flow_out += f; 108 flow_out += f; 88 if( flow_in == flow_out ) return flow_ou 109 if( flow_in == flow_out ) return flow_ou 89 } 110 } 90 } 111 } 91 } 112 } 92 blocked[v] = (flow_out==0); 113 blocked[v] = (flow_out==0); 93 return flow_out; 114 return flow_out; 94 } 115 } 95 }; 116 };