1 Тема от aza_inf

  • aza_inf
  • Участник
  • Неактивен
  • Зарегистрирован: 2009-06-30
  • Сообщений: 78

Тема: MaxFlow

Каким алгоритмом лучше решать задачи на макс. поток?
Например, при ограничениях V<=500, E<=10000

2 Ответ от KADR

  • KADR
  • Участник
  • Неактивен
  • Откуда: Киев
  • Зарегистрирован: 2009-06-25
  • Сообщений: 231

Re: MaxFlow

Я обычно пишу Диница и он на олимпиадных задачах очень редко ТЛит. Чаще наоборот, работает быстрее остального.

3 Ответ от MSDN Отредактировано MSDN (2010-08-30 05:16:12)

  • MSDN
  • Участник
  • Неактивен
  • Зарегистрирован: 2010-03-09
  • Сообщений: 40

Re: MaxFlow

Очень большое значение имеет величина потока. Мы вот недавно пропихнули поток на графе в 10000 вершин фордом фалкерсоном (всегда его пишем - просто в прикольной реализации)... потому что поток не большой был

4 Ответ от vanla

  • vanla
  • Участник
  • Неактивен
  • Зарегистрирован: 2011-02-07
  • Сообщений: 2

Re: MaxFlow

Кстати, мне кажется, что в статьях по потокам надо бы упомянуть про масштабирование. Это простенькое улучшение уж очень полезно.