equal
deleted
inserted
replaced
134 bfs_queue.pop(); |
134 bfs_queue.pop(); |
135 int l=level[v]+1; |
135 int l=level[v]+1; |
136 |
136 |
137 InEdgeIt e; |
137 InEdgeIt e; |
138 for(G.first(e,v); G.valid(e); G.next(e)) { |
138 for(G.first(e,v); G.valid(e); G.next(e)) { |
139 Node w=G.tail(e); |
139 Node w=G.source(e); |
140 if ( level[w] == n && w != s ) { |
140 if ( level[w] == n && w != s ) { |
141 bfs_queue.push(w); |
141 bfs_queue.push(w); |
142 Node first=level_list[l]; |
142 Node first=level_list[l]; |
143 if ( G.valid(first) ) left.set(first,w); |
143 if ( G.valid(first) ) left.set(first,w); |
144 right.set(w,first); |
144 right.set(w,first); |
152 OutEdgeIt e; |
152 OutEdgeIt e; |
153 for(G.first(e,s); G.valid(e); G.next(e)) |
153 for(G.first(e,s); G.valid(e); G.next(e)) |
154 { |
154 { |
155 T c=capacity[e]; |
155 T c=capacity[e]; |
156 if ( c == 0 ) continue; |
156 if ( c == 0 ) continue; |
157 Node w=G.head(e); |
157 Node w=G.target(e); |
158 if ( level[w] < n ) { |
158 if ( level[w] < n ) { |
159 if ( excess[w] == 0 && w!=t ) active[level[w]].push(w); |
159 if ( excess[w] == 0 && w!=t ) active[level[w]].push(w); |
160 flow.set(e, c); |
160 flow.set(e, c); |
161 excess.set(w, excess[w]+c); |
161 excess.set(w, excess[w]+c); |
162 } |
162 } |
180 int l=level[v]+1; |
180 int l=level[v]+1; |
181 |
181 |
182 InEdgeIt e; |
182 InEdgeIt e; |
183 for(G.first(e,v); G.valid(e); G.next(e)) { |
183 for(G.first(e,v); G.valid(e); G.next(e)) { |
184 if ( capacity[e] == flow[e] ) continue; |
184 if ( capacity[e] == flow[e] ) continue; |
185 Node w=G.tail(e); |
185 Node w=G.source(e); |
186 if ( level[w] == n && w != s ) { |
186 if ( level[w] == n && w != s ) { |
187 bfs_queue.push(w); |
187 bfs_queue.push(w); |
188 Node first=level_list[l]; |
188 Node first=level_list[l]; |
189 if ( G.valid(first) ) left.set(first,w); |
189 if ( G.valid(first) ) left.set(first,w); |
190 right.set(w,first); |
190 right.set(w,first); |
194 } |
194 } |
195 |
195 |
196 OutEdgeIt f; |
196 OutEdgeIt f; |
197 for(G.first(f,v); G.valid(f); G.next(f)) { |
197 for(G.first(f,v); G.valid(f); G.next(f)) { |
198 if ( 0 == flow[f] ) continue; |
198 if ( 0 == flow[f] ) continue; |
199 Node w=G.head(f); |
199 Node w=G.target(f); |
200 if ( level[w] == n && w != s ) { |
200 if ( level[w] == n && w != s ) { |
201 bfs_queue.push(w); |
201 bfs_queue.push(w); |
202 Node first=level_list[l]; |
202 Node first=level_list[l]; |
203 if ( G.valid(first) ) left.set(first,w); |
203 if ( G.valid(first) ) left.set(first,w); |
204 right.set(w,first); |
204 right.set(w,first); |
245 OutEdgeIt e; |
245 OutEdgeIt e; |
246 for(G.first(e,s); G.valid(e); G.next(e)) |
246 for(G.first(e,s); G.valid(e); G.next(e)) |
247 { |
247 { |
248 T rem=capacity[e]-flow[e]; |
248 T rem=capacity[e]-flow[e]; |
249 if ( rem == 0 ) continue; |
249 if ( rem == 0 ) continue; |
250 Node w=G.head(e); |
250 Node w=G.target(e); |
251 if ( level[w] < n ) { |
251 if ( level[w] < n ) { |
252 if ( excess[w] == 0 && w!=t ) active[level[w]].push(w); |
252 if ( excess[w] == 0 && w!=t ) active[level[w]].push(w); |
253 flow.set(e, capacity[e]); |
253 flow.set(e, capacity[e]); |
254 excess.set(w, excess[w]+rem); |
254 excess.set(w, excess[w]+rem); |
255 } |
255 } |
257 |
257 |
258 InEdgeIt f; |
258 InEdgeIt f; |
259 for(G.first(f,s); G.valid(f); G.next(f)) |
259 for(G.first(f,s); G.valid(f); G.next(f)) |
260 { |
260 { |
261 if ( flow[f] == 0 ) continue; |
261 if ( flow[f] == 0 ) continue; |
262 Node w=G.tail(f); |
262 Node w=G.source(f); |
263 if ( level[w] < n ) { |
263 if ( level[w] < n ) { |
264 if ( excess[w] == 0 && w!=t ) active[level[w]].push(w); |
264 if ( excess[w] == 0 && w!=t ) active[level[w]].push(w); |
265 excess.set(w, excess[w]+flow[f]); |
265 excess.set(w, excess[w]+flow[f]); |
266 flow.set(f, 0); |
266 flow.set(f, 0); |
267 } |
267 } |
301 int l=level[v]+1; |
301 int l=level[v]+1; |
302 |
302 |
303 InEdgeIt e; |
303 InEdgeIt e; |
304 for(G.first(e,v); G.valid(e); G.next(e)) { |
304 for(G.first(e,v); G.valid(e); G.next(e)) { |
305 if ( capacity[e] == flow[e] ) continue; |
305 if ( capacity[e] == flow[e] ) continue; |
306 Node u=G.tail(e); |
306 Node u=G.source(e); |
307 if ( level[u] >= n ) { |
307 if ( level[u] >= n ) { |
308 bfs_queue.push(u); |
308 bfs_queue.push(u); |
309 level.set(u, l); |
309 level.set(u, l); |
310 if ( excess[u] > 0 ) active[l].push(u); |
310 if ( excess[u] > 0 ) active[l].push(u); |
311 } |
311 } |
312 } |
312 } |
313 |
313 |
314 OutEdgeIt f; |
314 OutEdgeIt f; |
315 for(G.first(f,v); G.valid(f); G.next(f)) { |
315 for(G.first(f,v); G.valid(f); G.next(f)) { |
316 if ( 0 == flow[f] ) continue; |
316 if ( 0 == flow[f] ) continue; |
317 Node u=G.head(f); |
317 Node u=G.target(f); |
318 if ( level[u] >= n ) { |
318 if ( level[u] >= n ) { |
319 bfs_queue.push(u); |
319 bfs_queue.push(u); |
320 level.set(u, l); |
320 level.set(u, l); |
321 if ( excess[u] > 0 ) active[l].push(u); |
321 if ( excess[u] > 0 ) active[l].push(u); |
322 } |
322 } |
341 |
341 |
342 OutEdgeIt e; |
342 OutEdgeIt e; |
343 for(G.first(e,w); G.valid(e); G.next(e)) { |
343 for(G.first(e,w); G.valid(e); G.next(e)) { |
344 |
344 |
345 if ( flow[e] == capacity[e] ) continue; |
345 if ( flow[e] == capacity[e] ) continue; |
346 Node v=G.head(e); |
346 Node v=G.target(e); |
347 //e=wv |
347 //e=wv |
348 |
348 |
349 if( lev > level[v] ) { |
349 if( lev > level[v] ) { |
350 /*Push is allowed now*/ |
350 /*Push is allowed now*/ |
351 |
351 |
383 if ( exc > 0 ) { |
383 if ( exc > 0 ) { |
384 InEdgeIt e; |
384 InEdgeIt e; |
385 for(G.first(e,w); G.valid(e); G.next(e)) { |
385 for(G.first(e,w); G.valid(e); G.next(e)) { |
386 |
386 |
387 if( flow[e] == 0 ) continue; |
387 if( flow[e] == 0 ) continue; |
388 Node v=G.tail(e); |
388 Node v=G.source(e); |
389 //e=vw |
389 //e=vw |
390 |
390 |
391 if( lev > level[v] ) { |
391 if( lev > level[v] ) { |
392 /*Push is allowed now*/ |
392 /*Push is allowed now*/ |
393 |
393 |
567 Node w=queue.front(); |
567 Node w=queue.front(); |
568 queue.pop(); |
568 queue.pop(); |
569 |
569 |
570 OutEdgeIt e; |
570 OutEdgeIt e; |
571 for(G.first(e,w) ; G.valid(e); G.next(e)) { |
571 for(G.first(e,w) ; G.valid(e); G.next(e)) { |
572 Node v=G.head(e); |
572 Node v=G.target(e); |
573 if (!M[v] && flow[e] < capacity[e] ) { |
573 if (!M[v] && flow[e] < capacity[e] ) { |
574 queue.push(v); |
574 queue.push(v); |
575 M.set(v, true); |
575 M.set(v, true); |
576 } |
576 } |
577 } |
577 } |
578 |
578 |
579 InEdgeIt f; |
579 InEdgeIt f; |
580 for(G.first(f,w) ; G.valid(f); G.next(f)) { |
580 for(G.first(f,w) ; G.valid(f); G.next(f)) { |
581 Node v=G.tail(f); |
581 Node v=G.source(f); |
582 if (!M[v] && flow[f] > 0 ) { |
582 if (!M[v] && flow[f] > 0 ) { |
583 queue.push(v); |
583 queue.push(v); |
584 M.set(v, true); |
584 M.set(v, true); |
585 } |
585 } |
586 } |
586 } |
607 queue.pop(); |
607 queue.pop(); |
608 |
608 |
609 |
609 |
610 InEdgeIt e; |
610 InEdgeIt e; |
611 for(G.first(e,w) ; G.valid(e); G.next(e)) { |
611 for(G.first(e,w) ; G.valid(e); G.next(e)) { |
612 Node v=G.tail(e); |
612 Node v=G.source(e); |
613 if (!M[v] && flow[e] < capacity[e] ) { |
613 if (!M[v] && flow[e] < capacity[e] ) { |
614 queue.push(v); |
614 queue.push(v); |
615 M.set(v, true); |
615 M.set(v, true); |
616 } |
616 } |
617 } |
617 } |
618 |
618 |
619 OutEdgeIt f; |
619 OutEdgeIt f; |
620 for(G.first(f,w) ; G.valid(f); G.next(f)) { |
620 for(G.first(f,w) ; G.valid(f); G.next(f)) { |
621 Node v=G.head(f); |
621 Node v=G.target(f); |
622 if (!M[v] && flow[f] > 0 ) { |
622 if (!M[v] && flow[f] > 0 ) { |
623 queue.push(v); |
623 queue.push(v); |
624 M.set(v, true); |
624 M.set(v, true); |
625 } |
625 } |
626 } |
626 } |