Differences From Artifact [c6d3325f9b7a789b]:
- File
_lib/graph/maxFlow.cpp
- 2011-02-23 09:21:16 - part of checkin [4fd800b3a8] on branch trunk - Copied from private svn repository. (user: kinaba) [annotate]
- File
lib/graph/maxFlow.cpp
- 2011-02-23 11:18:09 - part of checkin [23dfcca431] on branch trunk - renamed _lib to lib (user: kinaba) [annotate]
To Artifact [296b9275312ebbf1]:
- File
lib/graph/maxFlow.cpp
- 2011-09-18 05:51:05 - part of checkin [11265aa172] on branch trunk - New-style maxflow. (user: kinaba) [annotate]
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 };