equal
deleted
inserted
replaced
1 // -*- C++ -*- |
1 // -*- C++ -*- |
|
2 |
|
3 //kerdesek: nem tudom lehet-e a |
|
4 //kieleket csak a legf n szintu pontokra nezni. |
|
5 |
2 /* |
6 /* |
3 preflow_push_hl.h |
7 preflow_push_hl.h |
4 by jacint. |
8 by jacint. |
5 Runs the highest label variant of the preflow push algorithm with |
9 Runs the highest label variant of the preflow push algorithm with |
6 running time O(n^2\sqrt(m)), and with the 'empty level' heuristic. |
10 running time O(n^2\sqrt(m)), and with the 'empty level' heuristic. |
114 |
118 |
115 |
119 |
116 /* Starting flow. It is everywhere 0 at the moment. */ |
120 /* Starting flow. It is everywhere 0 at the moment. */ |
117 for(OutEdgeIt e=G.template first<OutEdgeIt>(s); e.valid(); ++e) |
121 for(OutEdgeIt e=G.template first<OutEdgeIt>(s); e.valid(); ++e) |
118 { |
122 { |
119 if ( capacity.get(e) == 0 ) continue; |
123 T c=capacity.get(e); |
|
124 if ( c == 0 ) continue; |
120 NodeIt w=G.head(e); |
125 NodeIt w=G.head(e); |
121 if ( w!=s ) { |
126 if ( w!=s ) { |
122 if ( excess.get(w) == 0 && w!=t ) stack[level.get(w)].push(w); |
127 if ( excess.get(w) == 0 && w!=t ) stack[level.get(w)].push(w); |
123 flow.set(e, capacity.get(e)); |
128 flow.set(e, c); |
124 excess.set(w, excess.get(w)+capacity.get(e)); |
129 excess.set(w, excess.get(w)+c); |
125 } |
130 } |
126 } |
131 } |
127 |
132 |
128 /* |
133 /* |
129 End of preprocessing |
134 End of preprocessing |
142 |
147 |
143 NodeIt w=stack[b].top(); //w is a highest label active node. |
148 NodeIt w=stack[b].top(); //w is a highest label active node. |
144 stack[b].pop(); |
149 stack[b].pop(); |
145 int lev=level.get(w); |
150 int lev=level.get(w); |
146 int exc=excess.get(w); |
151 int exc=excess.get(w); |
147 int newlevel=2*n-2; //In newlevel we bound the next level of w. |
152 int newlevel=2*n; //In newlevel we bound the next level of w. |
148 |
153 //vagy MAXINT |
|
154 |
149 // if ( level.get(w) < n ) { //Nem tudom ez mukodik-e |
155 // if ( level.get(w) < n ) { //Nem tudom ez mukodik-e |
150 for(OutEdgeIt e=G.template first<OutEdgeIt>(w); e.valid(); ++e) { |
156 for(OutEdgeIt e=G.template first<OutEdgeIt>(w); e.valid(); ++e) { |
151 |
157 |
152 if ( flow.get(e) == capacity.get(e) ) continue; |
158 if ( flow.get(e) == capacity.get(e) ) continue; |
153 NodeIt v=G.head(e); |
159 NodeIt v=G.head(e); |