Блог пользователя Infoshoc

Автор Infoshoc, история, 8 лет назад, перевод, По-русски

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

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

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

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

  • Проголосовать: нравится
  • +10
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Автокомментарий: текст был переведен пользователем Infoshoc (оригинальная версия, переведенная версия, сравнить).

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

http://ideone.com/Q0nevm
разница в строке 108

»
8 лет назад, # |
Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

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