49 /// algorithms for finding a \ref min_cost_flow "minimum cost flow" |
49 /// algorithms for finding a \ref min_cost_flow "minimum cost flow" |
50 /// \cite amo93networkflows, \cite klein67primal, |
50 /// \cite amo93networkflows, \cite klein67primal, |
51 /// \cite goldberg89cyclecanceling. |
51 /// \cite goldberg89cyclecanceling. |
52 /// The most efficent one is the \ref CANCEL_AND_TIGHTEN |
52 /// The most efficent one is the \ref CANCEL_AND_TIGHTEN |
53 /// "Cancel-and-Tighten" algorithm, thus it is the default method. |
53 /// "Cancel-and-Tighten" algorithm, thus it is the default method. |
54 /// It runs in strongly polynomial time O(n<sup>2</sup>e<sup>2</sup>log(n)), |
54 /// It runs in strongly polynomial time O(n<sup>2</sup>m<sup>2</sup>log(n)), |
55 /// but in practice, it is typically orders of magnitude slower than |
55 /// but in practice, it is typically orders of magnitude slower than |
56 /// the scaling algorithms and \ref NetworkSimplex. |
56 /// the scaling algorithms and \ref NetworkSimplex. |
57 /// (For more information, see \ref min_cost_flow_algs "the module page".) |
57 /// (For more information, see \ref min_cost_flow_algs "the module page".) |
58 /// |
58 /// |
59 /// Most of the parameters of the problem (except for the digraph) |
59 /// Most of the parameters of the problem (except for the digraph) |
131 SIMPLE_CYCLE_CANCELING, |
131 SIMPLE_CYCLE_CANCELING, |
132 /// The "Minimum Mean Cycle-Canceling" algorithm, which is a |
132 /// The "Minimum Mean Cycle-Canceling" algorithm, which is a |
133 /// well-known strongly polynomial method |
133 /// well-known strongly polynomial method |
134 /// \cite goldberg89cyclecanceling. It improves along a |
134 /// \cite goldberg89cyclecanceling. It improves along a |
135 /// \ref min_mean_cycle "minimum mean cycle" in each iteration. |
135 /// \ref min_mean_cycle "minimum mean cycle" in each iteration. |
136 /// Its running time complexity is O(n<sup>2</sup>e<sup>3</sup>log(n)). |
136 /// Its running time complexity is O(n<sup>2</sup>m<sup>3</sup>log(n)). |
137 MINIMUM_MEAN_CYCLE_CANCELING, |
137 MINIMUM_MEAN_CYCLE_CANCELING, |
138 /// The "Cancel-and-Tighten" algorithm, which can be viewed as an |
138 /// The "Cancel-and-Tighten" algorithm, which can be viewed as an |
139 /// improved version of the previous method |
139 /// improved version of the previous method |
140 /// \cite goldberg89cyclecanceling. |
140 /// \cite goldberg89cyclecanceling. |
141 /// It is faster both in theory and in practice, its running time |
141 /// It is faster both in theory and in practice, its running time |
142 /// complexity is O(n<sup>2</sup>e<sup>2</sup>log(n)). |
142 /// complexity is O(n<sup>2</sup>m<sup>2</sup>log(n)). |
143 CANCEL_AND_TIGHTEN |
143 CANCEL_AND_TIGHTEN |
144 }; |
144 }; |
145 |
145 |
146 private: |
146 private: |
147 |
147 |
574 /// @{ |
574 /// @{ |
575 |
575 |
576 /// \brief Return the total cost of the found flow. |
576 /// \brief Return the total cost of the found flow. |
577 /// |
577 /// |
578 /// This function returns the total cost of the found flow. |
578 /// This function returns the total cost of the found flow. |
579 /// Its complexity is O(e). |
579 /// Its complexity is O(m). |
580 /// |
580 /// |
581 /// \note The return type of the function can be specified as a |
581 /// \note The return type of the function can be specified as a |
582 /// template parameter. For example, |
582 /// template parameter. For example, |
583 /// \code |
583 /// \code |
584 /// cc.totalCost<double>(); |
584 /// cc.totalCost<double>(); |