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

Implement mincostflow #25

Closed kenkoooo closed 4 years ago

kenkoooo commented 4 years ago

Port mincostflow from the AtCoder's library, resolved #21.

Questions

MiSawa commented 4 years ago

For Cap and Cost -- in theory we can use a different type for Cap, Cost and Result type where Result : From<Cap> + From<Cost>.... which can be useful for problems like this, though probably overkill for almost all other problems.

Another use case would be non-integral cost problems. Since having non-integral capacity is problematic for this algorithm, it would make sense to separate these two type params, and use Cost type for product of them. Actually floating point types in Rust doesn't implement Ord, so..... nevermind.

kenkoooo commented 4 years ago

For Cap and Cost -- in theory we can use a different type for Cap, Cost and Result type where Result : From<Cap> + From<Cost>.... which can be useful for problems like this, though probably overkill for almost all other problems.

~Another use case would be non-integral cost problems. Since having non-integral capacity is problematic for this algorithm, it would make sense to separate these two type params, and use Cost type for product of them.~ Actually floating point types in Rust doesn't implement Ord, so..... nevermind.

Thanks! Let's keep using a single type parameter for now.