The question arose, while solving [problem:100783D].↵
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
Вопрос вознпик, во время решения [problem:100783D].↵
В ту ночь когда мы прочитали её, моей первой мыслью был максимальный поток в единичной сети с ребрами из источника во все А, из А в B, из всех B в сток должен быть равен к-ву ч-к. Начали искать алгоритм который подходит к ограничениям и нашли что Диниц когда его использовать для максимального паросочетания в двудольном графе работает за O(sqrt(V)E). (
Ok I wrote Dinic almost like
Ок, реализовал я Диница почти как [e-maxx](http://e-maxx.ru/algo/dinic#13)
↵
Ok, said [user:AndreaB330,2016-05-27], 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.
↵
На это [user:AndreaB330,2016-05-27] спросил, почему я не написал Куна, я подумав об этом согласился что O(N^2) вообще нормально подходит и получил свой AC.↵
↵
Вопрос в том, что я такого страшного сделал (или не сделал) в Динице, что он не сработал как ожидаемо?↵
↵
Премного благодарствую :)
