equal
deleted
inserted
replaced
67 /// \ref CapacityScaling implements the capacity scaling version |
67 /// \ref CapacityScaling implements the capacity scaling version |
68 /// of the successive shortest path algorithm for finding a |
68 /// of the successive shortest path algorithm for finding a |
69 /// \ref min_cost_flow "minimum cost flow" \cite amo93networkflows, |
69 /// \ref min_cost_flow "minimum cost flow" \cite amo93networkflows, |
70 /// \cite edmondskarp72theoretical. It is an efficient dual |
70 /// \cite edmondskarp72theoretical. It is an efficient dual |
71 /// solution method, which runs in polynomial time |
71 /// solution method, which runs in polynomial time |
72 /// \f$O(e\log U (n+e)\log n)\f$, where <i>U</i> denotes the maximum |
72 /// \f$O(m\log U (n+m)\log n)\f$, where <i>U</i> denotes the maximum |
73 /// of node supply and arc capacity values. |
73 /// of node supply and arc capacity values. |
74 /// |
74 /// |
75 /// This algorithm is typically slower than \ref CostScaling and |
75 /// This algorithm is typically slower than \ref CostScaling and |
76 /// \ref NetworkSimplex, but in special cases, it can be more |
76 /// \ref NetworkSimplex, but in special cases, it can be more |
77 /// efficient than them. |
77 /// efficient than them. |
644 /// @{ |
644 /// @{ |
645 |
645 |
646 /// \brief Return the total cost of the found flow. |
646 /// \brief Return the total cost of the found flow. |
647 /// |
647 /// |
648 /// This function returns the total cost of the found flow. |
648 /// This function returns the total cost of the found flow. |
649 /// Its complexity is O(e). |
649 /// Its complexity is O(m). |
650 /// |
650 /// |
651 /// \note The return type of the function can be specified as a |
651 /// \note The return type of the function can be specified as a |
652 /// template parameter. For example, |
652 /// template parameter. For example, |
653 /// \code |
653 /// \code |
654 /// cs.totalCost<double>(); |
654 /// cs.totalCost<double>(); |