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