23dfcca431 2011-02-23 kinaba: 23dfcca431 2011-02-23 kinaba: //------------------------------------------------------------- 23dfcca431 2011-02-23 kinaba: // Dinic's Algorithm 23dfcca431 2011-02-23 kinaba: // O(V E) 23dfcca431 2011-02-23 kinaba: // 23dfcca431 2011-02-23 kinaba: // G : bidirectional (G[i].has(j) <==> G[j].has(i)) 23dfcca431 2011-02-23 kinaba: // F : flow-capacity F[i][j] = Capacity, F[j][i] = 0 23dfcca431 2011-02-23 kinaba: // 5e9a43e520 2019-11-16 kinaba: // Old versoin Verified by 23dfcca431 2011-02-23 kinaba: // - SRM 399 Div1 LV3 23dfcca431 2011-02-23 kinaba: // - PKU 1459 23dfcca431 2011-02-23 kinaba: // - CodeCraft 09 CUTS 23dfcca431 2011-02-23 kinaba: // - SRM 465 Div1 LV2 2034908d41 2012-05-20 kinaba: // - SRM 543 Div1 LV3 23dfcca431 2011-02-23 kinaba: //------------------------------------------------------------- 23dfcca431 2011-02-23 kinaba: 11265aa172 2011-09-18 kinaba: template<typename T> 11265aa172 2011-09-18 kinaba: class IdGen 23dfcca431 2011-02-23 kinaba: { 11265aa172 2011-09-18 kinaba: map<T, int> v2id_; 11265aa172 2011-09-18 kinaba: vector<T> id2v_; 11265aa172 2011-09-18 kinaba: public: 11265aa172 2011-09-18 kinaba: int v2id(const T& v) { 11265aa172 2011-09-18 kinaba: if( !v2id_.count(v) ) { v2id_[v] = size(); id2v_.push_back(v); } 11265aa172 2011-09-18 kinaba: return v2id_[v]; 23dfcca431 2011-02-23 kinaba: } 11265aa172 2011-09-18 kinaba: const T& id2v(int i) const { return id2v_[i]; } 11265aa172 2011-09-18 kinaba: int size() const { return id2v_.size(); } 11265aa172 2011-09-18 kinaba: }; 23dfcca431 2011-02-23 kinaba: 5e9a43e520 2019-11-16 kinaba: template<typename Vert, typename Flow, int NV=50*50*8+2> 11265aa172 2011-09-18 kinaba: class MaxFlow 23dfcca431 2011-02-23 kinaba: { 5e9a43e520 2019-11-16 kinaba: typedef int Edge; 5e9a43e520 2019-11-16 kinaba: 5e9a43e520 2019-11-16 kinaba: vector<int> G[NV]; 5e9a43e520 2019-11-16 kinaba: vector<Flow> F; 5e9a43e520 2019-11-16 kinaba: 11265aa172 2011-09-18 kinaba: IdGen<Vert> idgen; 5e9a43e520 2019-11-16 kinaba: map<pair<int,int>, Edge> edge_id; 5e9a43e520 2019-11-16 kinaba: vector<int> Edge_to; 5e9a43e520 2019-11-16 kinaba: vector<Edge> Edge_rev; 11265aa172 2011-09-18 kinaba: 11265aa172 2011-09-18 kinaba: public: 5e9a43e520 2019-11-16 kinaba: void add( Vert s_, Vert t_, Flow f ) 11265aa172 2011-09-18 kinaba: { 11265aa172 2011-09-18 kinaba: const int s = idgen.v2id(s_), t = idgen.v2id(t_); 5e9a43e520 2019-11-16 kinaba: if(!edge_id.count(make_pair(s,t))) { 5e9a43e520 2019-11-16 kinaba: const int e = int(edge_id.size()); 5e9a43e520 2019-11-16 kinaba: edge_id[make_pair(s,t)] = e; 5e9a43e520 2019-11-16 kinaba: edge_id[make_pair(t,s)] = e+1; 5e9a43e520 2019-11-16 kinaba: G[s].push_back(e); 5e9a43e520 2019-11-16 kinaba: G[t].push_back(e+1); 5e9a43e520 2019-11-16 kinaba: F.push_back(0); 5e9a43e520 2019-11-16 kinaba: F.push_back(0); 5e9a43e520 2019-11-16 kinaba: Edge_rev.push_back(e+1); 5e9a43e520 2019-11-16 kinaba: Edge_rev.push_back(e); 5e9a43e520 2019-11-16 kinaba: Edge_to.push_back(t); 5e9a43e520 2019-11-16 kinaba: Edge_to.push_back(s); 5e9a43e520 2019-11-16 kinaba: } 5e9a43e520 2019-11-16 kinaba: const Edge e = edge_id[make_pair(s,t)]; 5e9a43e520 2019-11-16 kinaba: F[e] = min(F[e]+f, INF); 11265aa172 2011-09-18 kinaba: } 11265aa172 2011-09-18 kinaba: 11265aa172 2011-09-18 kinaba: Flow calc( Vert s_, Vert t_ ) 11265aa172 2011-09-18 kinaba: { 11265aa172 2011-09-18 kinaba: const int S = idgen.v2id(s_), D = idgen.v2id(t_); 11265aa172 2011-09-18 kinaba: for( Flow total=0 ;; ) { 11265aa172 2011-09-18 kinaba: // Do BFS and compute the level for each node. 11265aa172 2011-09-18 kinaba: int LV[NV] = {0}; 11265aa172 2011-09-18 kinaba: vector<int> Q(1, S); 11265aa172 2011-09-18 kinaba: for(int lv=1; !Q.empty(); ++lv) { 11265aa172 2011-09-18 kinaba: vector<int> Q2; 11265aa172 2011-09-18 kinaba: for(size_t i=0; i!=Q.size(); ++i) { 5e9a43e520 2019-11-16 kinaba: const vector<Edge>& ne = G[Q[i]]; 5e9a43e520 2019-11-16 kinaba: for(size_t j=0; j!=ne.size(); ++j) { 5e9a43e520 2019-11-16 kinaba: Edge e = ne[j]; 5e9a43e520 2019-11-16 kinaba: int t = Edge_to[e]; 5e9a43e520 2019-11-16 kinaba: if( F[e] && !LV[t] && t!=S ) 5e9a43e520 2019-11-16 kinaba: LV[t]=lv, Q2.push_back(t); 5e9a43e520 2019-11-16 kinaba: } 11265aa172 2011-09-18 kinaba: } 11265aa172 2011-09-18 kinaba: Q.swap(Q2); 23dfcca431 2011-02-23 kinaba: } 11265aa172 2011-09-18 kinaba: 11265aa172 2011-09-18 kinaba: // Destination is now unreachable. Done. 11265aa172 2011-09-18 kinaba: if( !LV[D] ) 11265aa172 2011-09-18 kinaba: return total; 23dfcca431 2011-02-23 kinaba: 11265aa172 2011-09-18 kinaba: // Iterating DFS. 11265aa172 2011-09-18 kinaba: bool blocked[NV] = {}; 5e9a43e520 2019-11-16 kinaba: total += dinic_dfs( S, D, LV, INF, blocked ); 11265aa172 2011-09-18 kinaba: } 11265aa172 2011-09-18 kinaba: } 23dfcca431 2011-02-23 kinaba: 11265aa172 2011-09-18 kinaba: private: 11265aa172 2011-09-18 kinaba: Flow dinic_dfs( int v, int D, int LV[], Flow flow_in, bool blocked[] ) 11265aa172 2011-09-18 kinaba: { 11265aa172 2011-09-18 kinaba: Flow flow_out = 0; 11265aa172 2011-09-18 kinaba: for(size_t i=0; i!=G[v].size(); ++i) { 5e9a43e520 2019-11-16 kinaba: Edge e = G[v][i]; 5e9a43e520 2019-11-16 kinaba: int u = Edge_to[e]; 5e9a43e520 2019-11-16 kinaba: if( LV[v]+1==LV[u] && F[e] ) { 5e9a43e520 2019-11-16 kinaba: Flow f = min(flow_in-flow_out, F[e]); 11265aa172 2011-09-18 kinaba: if( u==D || !blocked[u] && (f=dinic_dfs(u,D,LV,f,blocked))>0 ) { 5e9a43e520 2019-11-16 kinaba: F[e] -= f; 5e9a43e520 2019-11-16 kinaba: F[Edge_rev[e]] += f; 11265aa172 2011-09-18 kinaba: flow_out += f; 11265aa172 2011-09-18 kinaba: if( flow_in == flow_out ) return flow_out; 11265aa172 2011-09-18 kinaba: } 11265aa172 2011-09-18 kinaba: } 11265aa172 2011-09-18 kinaba: } 11265aa172 2011-09-18 kinaba: blocked[v] = (flow_out==0); 11265aa172 2011-09-18 kinaba: return flow_out; 23dfcca431 2011-02-23 kinaba: } 11265aa172 2011-09-18 kinaba: };