equal
deleted
inserted
replaced
23 */ |
23 */ |
24 |
24 |
25 #ifndef PREFLOW_PUSH_HL_H |
25 #ifndef PREFLOW_PUSH_HL_H |
26 #define PREFLOW_PUSH_HL_H |
26 #define PREFLOW_PUSH_HL_H |
27 |
27 |
28 //#include <algorithm> |
28 #define A 1 |
|
29 |
29 #include <vector> |
30 #include <vector> |
30 #include <stack> |
31 #include <stack> |
31 |
32 |
32 #include <reverse_bfs.h> |
33 #include <reverse_bfs.h> |
33 |
34 |
62 The run() function runs the highest label preflow-push, |
63 The run() function runs the highest label preflow-push, |
63 running time: O(n^2\sqrt(m)) |
64 running time: O(n^2\sqrt(m)) |
64 */ |
65 */ |
65 void run() { |
66 void run() { |
66 |
67 |
|
68 std::cout<<"A is "<<A<<" "; |
|
69 |
67 typename Graph::NodeMap<int> level(G); |
70 typename Graph::NodeMap<int> level(G); |
68 typename Graph::NodeMap<T> excess(G); |
71 typename Graph::NodeMap<T> excess(G); |
69 |
72 |
70 int n=G.nodeNum(); |
73 int n=G.nodeNum(); |
71 int b=n-2; |
74 int b=n-2; |
218 level.set(w,++newlevel); |
221 level.set(w,++newlevel); |
219 |
222 |
220 if ( oldlevel < n ) { |
223 if ( oldlevel < n ) { |
221 --numb[oldlevel]; |
224 --numb[oldlevel]; |
222 |
225 |
223 if ( !numb[oldlevel] ) { //If the level of w gets empty. |
226 if ( !numb[oldlevel] && oldlevel < A*n ) { //If the level of w gets empty. |
224 |
227 |
225 for (EachNodeIt v=G.template first<EachNodeIt>(); v.valid() ; ++v) { |
228 for (EachNodeIt v=G.template first<EachNodeIt>(); v.valid() ; ++v) { |
226 if (level.get(v) > oldlevel && level.get(v) < n ) level.set(v,n); |
229 if (level.get(v) > oldlevel && level.get(v) < n ) level.set(v,n); |
227 } |
230 } |
228 for (int i=oldlevel+1 ; i!=n ; ++i) numb[i]=0; |
231 for (int i=oldlevel+1 ; i!=n ; ++i) numb[i]=0; |
266 |
269 |
267 /* |
270 /* |
268 For the maximum flow x found by the algorithm, it returns the flow value on Edge e, i.e. x(e). |
271 For the maximum flow x found by the algorithm, it returns the flow value on Edge e, i.e. x(e). |
269 */ |
272 */ |
270 |
273 |
271 T flowonEdge(EdgeIt e) { |
274 T flowonedge(EdgeIt e) { |
272 return flow.get(e); |
275 return flow.get(e); |
273 } |
276 } |
274 |
277 |
275 |
278 |
276 |
279 |