Dinic vs Kuhn

Revision ru1, by Infoshoc, 2016-05-27 22:04:34

Здравствуйте все! Вопрос вознпик, во время решения 100783D - Book Club. В ту ночь когда мы прочитали её, моей первой мыслью был максимальный поток в единичной сети с ребрами из источника во все А, из А в B, из всех B в сток должен быть равен к-ву ч-к. Начали искать алгоритм который подходит к ограничениям и нашли что Диниц когда его использовать для максимального паросочетания в двудольном графе работает за O(sqrt(V)E). (Вау подходит, ведь E<=N итого O(N^1.5)). Ок, реализовал я Диница почти как e-maxx и моя реализация упала на 13-ом тесте с TL.

На это AndrewB330 спросил, почему я не написал Куна, я подумав об этом согласился что O(N^2) вообще нормально подходит и получил свой AC.

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

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

Tags диниц, алгоритм куна, граф, паросочетания

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)