Здравствуйте все! Вопрос вознпик, во время решения 100783D - Book Club. В ту ночь когда мы прочитали её, моей первой мыслью был максимальный поток в единичной сети с ребрами из источника во все А, из А в B, из всех B в сток должен быть равен к-ву ч-к. Начали искать алгоритм который подходит к ограничениям и нашли что Диниц когда его использовать для максимального паросочетания в двудольном графе работает за O(sqrt(V)E). (Вау подходит, ведь E<=N итого O(N^1.5)). Ок, реализовал я Диница почти как e-maxx и моя реализация упала на 13-ом тесте с TL.
На это AndrewB330 спросил, почему я не написал Куна, я подумав об этом согласился что O(N^2) вообще нормально подходит и получил свой AC.
Вопрос в том, что я такого страшного сделал (или не сделал) в Динице, что он не сработал как ожидаемо?
Премного благодарствую :)
Автокомментарий: текст был переведен пользователем Infoshoc (оригинальная версия, переведенная версия, сравнить).
http://ideone.com/Q0nevm
разница в строке 108
Глаз алмаз! Спасибо!
You should be doing DFS while augmenting is greater than 0, not only once per BFS.
PS: That's the mistake I was doing before which was preventing me from solving FASTFLOW on SPOJ so I knew what to look for :D