Dinic vs Kuhn

Revision en1, by Infoshoc, 2016-05-27 21:56:53

Hello everyone! The question arose, while solving 100783D - Book Club. Somehow it was night when we read it, and first thought that got to my mind: in unit network with source, edges from source to all A's, edges from A to B and from B's to sink, flow should be equal to number of people. I started to search max flow algorithm which suits to limits and found out that Dinic used for solving bipartite problem takes O(sqrt(V)E) (Wow this is the case with E maximum N we can get O(N^1.5)). Ok I wrote Dinic almost like e-maxx it and it got as far as test 13 with TL.

Ok, said AndrewB330, why didn't you wrote Khun. I thought about it, and agreed that yes O(N^2) suits me. And got bloody AC.

The question is: what so horrible I did in Dinic or what should I have done so it worked as expected?

Thank you, community.

Tags dinic, kuhn, graph, bipartite matching

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru1 Russian Infoshoc 2016-05-27 22:04:34 922 Первая редакция перевода на Русский
en1 English Infoshoc 2016-05-27 21:56:53 917 Initial revision (published)