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

Максимальный поток + смежные темы
Автор Krot, 15 лет назад, По-русски
Максимальный поток, поток с ограничениями, поток минимальной стоимости, паросочетания, мин. разрез и т д. 

Никак немогу найти задач на эти темы. Точнее никак не получается в задачах этого увидеть. Покидайте пожалуйста, кому не сложно ссылки на задачи (например с того же тимуса) на эти темы.

А то все примеры, какие я видел - так это "симпатичные таблицы")

UPD. Всем спасибо!
  • Проголосовать: нравится
  • +7
  • Проголосовать: не нравится

15 лет назад, скрыть # |
 
Проголосовать: нравится +6 Проголосовать: не нравится
Навскидку, что решал потоками.

http://acm.timus.ru/problem.aspx?space=1&num=1076
http://acm.timus.ru/problem.aspx?space=1&num=1109
http://acm.timus.ru/problem.aspx?space=1&num=1237
http://acm.timus.ru/problem.aspx?space=1&num=1277
http://acm.timus.ru/problem.aspx?space=1&num=1421
http://acm.timus.ru/problem.aspx?space=1&num=1721
→ Ответить
15 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +5 Проголосовать: не нравится
Решал потоком это:
Здесь же и хорошая задачка на паросочетания:

UPD: Пытался дописать в ответ, но глюкануло, как можете видеть.
http://ipc.susu.ac.ru/210-2.html?problem=1502
Вот такая задачка, друг нашёл в ней неочевидный поток :)
Хотя тут решение может быть более "прямым", думаю, она всё-таки в тему.
→ Ответить
15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
→ Ответить
15 лет назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится
На acm.sgu.ru очень много задач на потоки и связанное с ними.
Вот те которые мне нравятся оттуда:
→ Ответить
15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
→ Ответить
  • 15 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится
    Спасибо всем, интересные задачи, если еще что-то "необычное" с виду никак не напоминающее потоки будет, скиньте сюда если не сложно. Один маленький вопрос есть: в некоторых задачах с виду ограничения такие, что решение за O(n^3) не должно проходить, тем не менее все ок. Это связано с тем, что в этих задачах "хорошая" сеть получается?
    → Ответить
    • 15 лет назад, скрыть # ^ |
      ← Rev. 2  
      Проголосовать: нравится +1 Проголосовать: не нравится
      К разным задачам нужно применять оптимальный алгоритм. Где-то нужен Диница за О(V^2*E), где-то Форда-Фалкерсона за O(V^2 * FLOW), где-то Эдмондса-Карпа за O(min( V*E^2, E*FLOW )). Например, в задаче 1721 на тимусе оптимально писать алгоритм Куна (нахождение максимального паросочетания за O(V*E)) - сведение задачи к потокам не пройдет у меня не прошло

      → Ответить
      • 15 лет назад, скрыть # ^ |
         
        Проголосовать: нравится 0 Проголосовать: не нравится
        Странно, у меня как раз наоборот вышло: поиск паросочетания привел к TLE, а поток прошел.
        → Ответить
      • 15 лет назад, скрыть # ^ |
         
        Проголосовать: нравится 0 Проголосовать: не нравится
        сведение задачи к потокам конечно же должно пройти, ведь Алгоритм Диница на графе для поиска максимального паросочетания, будет работать за O(E * Sqrt(V)), этот алгоритм поиска максимального паросочетания также известен как алгоритм Хопкрофта-Карпа.
        → Ответить
    • 15 лет назад, скрыть # ^ |
      ← Rev. 2  
      Проголосовать: нравится 0 Проголосовать: не нравится
      → Ответить
    • 15 лет назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится
      → Ответить
15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
→ Ответить
15 лет назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится
ВКОШП-2009
Задача A "Поедание сыра"
→ Ответить
15 лет назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится
Ну и еще 5 задач в догонку.
→ Ответить
15 лет назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится
Ну еще со сферы
→ Ответить