Dinic vs Kuhn
Разница между en1 и ru1, 922 символ(ов) изменены
Hello everyone!↵
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). (Wow this is the case with E maximum N we can get O(N^1.5)).↵
Ok I wrote Dinic almost like
Вау подходит, ведь E<=N итого O(N^1.5)).↵
Ок, реализовал я Диница почти как
 [e-maxx](http://e-maxx.ru/algo/dinic#13) [itи [моя реализация](http://ideone.com/Y2YdTa) and it got as far as test 13 with TL.↵

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.
упала на 13-ом тесте с TL.↵

На это [user:AndreaB330,2016-05-27] спросил, почему я не написал Куна, я подумав об этом согласился что  O(N^2) вообще нормально подходит и получил свой AC.↵

Вопрос в том, что я такого страшного сделал (или не сделал)  в Динице, что он не сработал как ожидаемо?↵

Премного благодарствую :)

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru1 Русский Infoshoc 2016-05-27 22:04:34 922 Первая редакция перевода на Русский
en1 Английский Infoshoc 2016-05-27 21:56:53 917 Initial revision (published)