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 9 // Verified by
10 10 // - SRM 399 Div1 LV3
11 11 // - PKU 1459
12 12 // - CodeCraft 09 CUTS
13 13 // - SRM 465 Div1 LV2
14 14 //-------------------------------------------------------------
15 15
16 -static const int NV = 512;
17 -typedef int flow;
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[] )
16 +template<typename T>
17 +class IdGen
26 18 {
27 - flow flow_out = 0;
28 - for(int i=0; i!=G[v].size(); ++i) {
29 - int u = G[v][i];
30 - if( LV[v]+1==LV[u] && F[v][u] ) {
31 - flow f = min(flow_in-flow_out, F[v][u]);
32 - if( u==D || !blocked[u] && (f=dinic_dfs(G,F,u,D,LV,f,blocked)) ) {
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 - }
19 + map<T, int> v2id_;
20 + vector<T> id2v_;
21 +public:
22 + int v2id(const T& v) {
23 + if( !v2id_.count(v) ) { v2id_[v] = size(); id2v_.push_back(v); }
24 + return v2id_[v];
39 25 }
40 - blocked[v] = (flow_out==0);
41 - return flow_out;
42 -}
26 + const T& id2v(int i) const { return id2v_[i]; }
27 + int size() const { return id2v_.size(); }
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 {
46 - for( flow total=0 ;; ) {
47 - int LV[NV] = {0};
48 - vector<int> Q(1, S);
49 - for(int lv=1; !Q.empty(); ++lv) {
50 - vector<int> Q2;
51 - for(int i=0; i!=Q.size(); ++i) {
52 - edges& ne = G[Q[i]];
53 - for(int j=0; j!=ne.size(); ++j)
54 - if( F[Q[i]][ne[j]] && !LV[ne[j]] && ne[j]!=S )
55 - LV[ne[j]]=lv, Q2.push_back(ne[j]);
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_);
50 + for( Flow total=0 ;; ) {
51 + // Do BFS and compute the level for each node.
52 + int LV[NV] = {0};
53 + vector<int> Q(1, S);
54 + for(int lv=1; !Q.empty(); ++lv) {
55 + vector<int> Q2;
56 + for(size_t i=0; i!=Q.size(); ++i) {
57 + const vector<int>& ne = G[Q[i]];
58 + for(size_t j=0; j!=ne.size(); ++j)
59 + if( F[Q[i]][ne[j]] && !LV[ne[j]] && ne[j]!=S )
60 + LV[ne[j]]=lv, Q2.push_back(ne[j]);
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] )
61 - return total;
69 + // Iterating DFS.
70 + bool blocked[NV] = {};
71 + total += dinic_dfs( S, D, LV, 0x7fffffff, blocked );
72 + }
73 + }
62 74
63 - int blocked[NV] = {};
64 - total += dinic_dfs( G, F, S, D, LV, 0x7fffffff, blocked );
75 +private:
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,blocked))>0 ) {
84 + F[v][u] -= f;
85 + F[u][v] += f;
86 + flow_out += f;
87 + if( flow_in == flow_out ) return flow_out;
88 + }
89 + }
90 + }
91 + blocked[v] = (flow_out==0);
92 + return flow_out;
65 93 }
66 -}
94 +};