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