equal
deleted
inserted
replaced
94 /// "minimum cost flow" \ref amo93networkflows, \ref goldberg90approximation, |
94 /// "minimum cost flow" \ref amo93networkflows, \ref goldberg90approximation, |
95 /// \ref goldberg97efficient, \ref bunnagel98efficient. |
95 /// \ref goldberg97efficient, \ref bunnagel98efficient. |
96 /// It is a highly efficient primal-dual solution method, which |
96 /// It is a highly efficient primal-dual solution method, which |
97 /// can be viewed as the generalization of the \ref Preflow |
97 /// can be viewed as the generalization of the \ref Preflow |
98 /// "preflow push-relabel" algorithm for the maximum flow problem. |
98 /// "preflow push-relabel" algorithm for the maximum flow problem. |
|
99 /// It is a polynomial algorithm, its running time complexity is |
|
100 /// \f$O(n^2e\log(nK))\f$, where <i>K</i> denotes the maximum arc cost. |
99 /// |
101 /// |
100 /// In general, \ref NetworkSimplex and \ref CostScaling are the fastest |
102 /// In general, \ref NetworkSimplex and \ref CostScaling are the fastest |
101 /// implementations available in LEMON for solving this problem. |
103 /// implementations available in LEMON for solving this problem. |
102 /// (For more information, see \ref min_cost_flow_algs "the module page".) |
104 /// (For more information, see \ref min_cost_flow_algs "the module page".) |
103 /// |
105 /// |
1267 while (_buckets[r] != bucket_end) { |
1269 while (_buckets[r] != bucket_end) { |
1268 // Remove the first node from the current bucket |
1270 // Remove the first node from the current bucket |
1269 int u = _buckets[r]; |
1271 int u = _buckets[r]; |
1270 _buckets[r] = _bucket_next[u]; |
1272 _buckets[r] = _bucket_next[u]; |
1271 |
1273 |
1272 // Search the incomming arcs of u |
1274 // Search the incoming arcs of u |
1273 LargeCost pi_u = _pi[u]; |
1275 LargeCost pi_u = _pi[u]; |
1274 int last_out = _first_out[u+1]; |
1276 int last_out = _first_out[u+1]; |
1275 for (int a = _first_out[u]; a != last_out; ++a) { |
1277 for (int a = _first_out[u]; a != last_out; ++a) { |
1276 int ra = _reverse[a]; |
1278 int ra = _reverse[a]; |
1277 if (_res_cap[ra] > 0) { |
1279 if (_res_cap[ra] > 0) { |