89 /// \brief Implementation of the Cost Scaling algorithm for |
89 /// \brief Implementation of the Cost Scaling algorithm for |
90 /// finding a \ref min_cost_flow "minimum cost flow". |
90 /// finding a \ref min_cost_flow "minimum cost flow". |
91 /// |
91 /// |
92 /// \ref CostScaling implements a cost scaling algorithm that performs |
92 /// \ref CostScaling implements a cost scaling algorithm that performs |
93 /// push/augment and relabel operations for finding a \ref min_cost_flow |
93 /// push/augment and relabel operations for finding a \ref min_cost_flow |
94 /// "minimum cost flow" \cite amo93networkflows, \cite goldberg90approximation, |
94 /// "minimum cost flow" \cite amo93networkflows, |
|
95 /// \cite goldberg90approximation, |
95 /// \cite goldberg97efficient, \cite bunnagel98efficient. |
96 /// \cite goldberg97efficient, \cite bunnagel98efficient. |
96 /// It is a highly efficient primal-dual solution method, which |
97 /// It is a highly efficient primal-dual solution method, which |
97 /// can be viewed as the generalization of the \ref Preflow |
98 /// can be viewed as the generalization of the \ref Preflow |
98 /// "preflow push-relabel" algorithm for the maximum flow problem. |
99 /// "preflow push-relabel" algorithm for the maximum flow problem. |
99 /// It is a polynomial algorithm, its running time complexity is |
100 /// It is a polynomial algorithm, its running time complexity is |
211 typedef std::vector<int> IntVector; |
212 typedef std::vector<int> IntVector; |
212 typedef std::vector<Value> ValueVector; |
213 typedef std::vector<Value> ValueVector; |
213 typedef std::vector<Cost> CostVector; |
214 typedef std::vector<Cost> CostVector; |
214 typedef std::vector<LargeCost> LargeCostVector; |
215 typedef std::vector<LargeCost> LargeCostVector; |
215 typedef std::vector<char> BoolVector; |
216 typedef std::vector<char> BoolVector; |
216 // Note: vector<char> is used instead of vector<bool> for efficiency reasons |
217 // Note: vector<char> is used instead of vector<bool> |
|
218 // for efficiency reasons |
217 |
219 |
218 private: |
220 private: |
219 |
221 |
220 template <typename KT, typename VT> |
222 template <typename KT, typename VT> |
221 class StaticVectorMap { |
223 class StaticVectorMap { |