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

Автор Mano, история, 6 лет назад, По-русски
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

Автор Mano, история, 7 лет назад, По-английски

Всем привет!) Расскажите пожалуйста как решались задачи с минувшего четвертьфинала в Санкт-Петербурге (4 ноября). Интересуют F, G, H.

Полный текст и комментарии »

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

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

Hello everybody! Can anyone share his good implementation min cost max flow algorithm in some problem or give a link to any problem on cf containing this algorithm. I have seen only http://e-maxx.ru/algo/min_cost_flow this implementation but not sure about asymptotics of it. Maybe anyone write it with Ford Bellman algorithm or something else? Would be very grateful :)

Полный текст и комментарии »

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

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

Возможно довольно глупый вопрос, но очень хочелось бы понять одну вещь, связанную с поиском макс. потока в графе. В алгоритме Форда Фалкерсона как в принципе и в алгоритме Диница мы ищем какой-то увеличивающий поток в остаточной сети и вот тут довольно магически выглядит возможность увеличивать поток, уменьшая предыдущий, т.е. например когда по ребру в одну сторону течёт flow < capacity, а в обратную течёт -flow < 0 и мы можем увеличить поток тем, что отменим этот, т.е. увеличить -flow в обратном направлении и уменьшить flow в прямом. Почему при этом не страдает первоначальный поток, который мы нашли?

Полный текст и комментарии »

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

Автор Mano, 10 лет назад, По-русски

В теме http://mirror.codeforces.com/blog/entry/17502 много сообщений... Решил спросить в новом разделе... Подскажите пожалуйста, как решаются задачи B, E и F?

Полный текст и комментарии »

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