atcoder/ac-library

Minimum cost flow algorithm

celiopassos opened this issue · 2 comments

celiopassos commented

Hello.

Is there any place I can learn about the minimum cost flow algorithm which is in the library?

Edit: Actually, it seems to be the same algorithm in this topcoder tutorial. However, they claim the complexity is O(nmFlogn) instead of O(F(n+m)logn). Which one should I trust? xD

yosupo06 commented

As far as I know, AtCoder doesn't have any resources to learn minimum cost flow algorithm. I guess there are many usefull lecture notes, books or something becuase minimum cost flow algorithm is quite famous.

Our time complexity is correct, O(F(n+m)logn).

yosupo06 commented

#57 I notice the time complexity is wrong (not O(F(n+m)logn), but O(F(n+m)logm))... thanks!