• Зарегистрирован: 2009-07-24
  • Сообщений: 12

Тема: Задачи с NEERC 2009

Кто-нибудь может объяснить как решались задачи с NEERC 2009?
Наибольший интерес представляет задача I.
Там нужно было покрыть ациклич. граф минимальным количеством путей( пути могут пересекаться по вершинам), на этом сайте есть подобный алгоритм но в нем пути не пересекаются. Этот алгоритм как-то связан с этой задачей?

2 Ответ от cmd

  • cmd
  • Участник
  • Неактивен
  • Откуда: Волжский
  • Зарегистрирован: 2009-06-11
  • Сообщений: 35

Re: Задачи с NEERC 2009

Поток с ограничениями на нижнии пропускные способности нужен (http://e-maxx.ru/algo/flow_with_limits).

  • Зарегистрирован: 2009-07-24
  • Сообщений: 12

Re: Задачи с NEERC 2009

Можно поконкретней? Как расставлять ограничения?

4 Ответ от denton

  • denton
  • Участник
  • Неактивен
  • Откуда: Санкт-Петербург
  • Зарегистрирован: 2009-07-05
  • Сообщений: 13

Re: Задачи с NEERC 2009

У каждого ребра нижнее ограничение пропускной способности 1 (это означает, что поток по этому ребру хотя бы 1, т.е. мы хотя бы раз пройдём по нему), верхнее какое угодно. В графе несколько истоков (понятно каких) + нужно добавить сток (и рёбра в него из всех вершин пропускной способности от 0 до бесконечности). В этом графе нужно найти минимальный поток. Как это делать, описано в статье Макса.