rust-lang-ja / ac-library-rs

ac-library-rs is a rust port of AtCoder Library (ACL).
Creative Commons Zero v1.0 Universal
225 stars 27 forks source link

MinCostFlow uses too small inifinity value #88

Closed MiSawa closed 3 years ago

MiSawa commented 3 years ago

In the original implementation, dist array in a dual refinement process is initialized with numeric_limits<T>::max(). Though in our implementation, we calculate the sum of cost among all the edges, and use that sum to initialize dist array, since we don't have trait that returns the maximum possible value of T. Though there can be a shortest path which costs the sum of all the edges, e.g. in case all but one edge have cost 0, and in that case we don't update the shortest path tree, which makes the algorithm stop prematurely.

Initializing cost_sum by 1 should solve the issue, though we might want another name for the variable. Picked from a slack thread.

MiSawa commented 3 years ago

Just noticed that we have a trait BoundedAbove now.