Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 16.08.2010, 14:20
Новичок

Отправить личное сообщение для lenny Посмотреть профиль Найти все сообщения от lenny
 
Регистрация: 16.08.2010
Сообщений: 1

Задача на минимальное остовное дерево (предположительно)
Здравствуйте! Есть следующая задача:
У фермера есть N полей (1 <= N <= 400), необходимо соединить их дорожками так, чтобы всегда был путь от любого поля к любому. Могут быть построены M (1 <= M <= 10,000) двунаправленных дорожек. Необходимо завершить проект с минимальными затратами денег. Формируется фирма, которая специализируется на постройке дорог. Фирма берется только за работу, которая принесет им прибыль.
Фирма договаривается об оплате F (1 <= F <= 2,000,000,000), которую им заплатят за восстановление дорог. Им дается таблица возможных дорог, время (в часах) на построение каждой дороги (1<=t<=2,000,000,000) и стоимость построения дороги (1<=c<=2,000,000,000). Таблица может содержать более одной дороги, соединяющей одну и ту же пару полей. Всегда возможно соединить все поля по заданным входным данным, хотя это может быть и не выгодно.
Определите значение максимальной прибыли, которую может принести постройка дорог на ферме.
Прибыль вычисляется по формуле (F-C)/T, где F - оговоренная сумма оплаты, С - сумма стоимостей построенных дорог, T - время, затраченное на построение дорог в сумме.

Так вот, необходимо соединить все поля так, чтобы максимизировать прибыль. Кажется, что это задача на нахождение минимального остовного дерева, но меня сбивает с толку необходимость учитывать два параметра для каждой дороги (c и t). И, соответственно, эту задачу у меня решить никак не получается. Источник задачи неизвестен (нашел у себя на харде в текстовом файле), гугление также ни к чему не привело.
  #2  
Старый 16.08.2010, 19:31
гость

 
Сообщений: n/a

Цитата:
Прибыль вычисляется по формуле (F-C)/T, где F - оговоренная сумма оплаты, С - сумма стоимостей построенных дорог, T - время, затраченное на построение дорог в сумме.
Воспользуемся двоичный поиск для максимизации величины (F-sum(c))/sum(t). (Я буду писать sum(c)=C и sum(t)=T, где суммы - по выбранным ребрам.)

Ключевой возникающий вопрос в этом алгоритме - проверить, можно ли выбрать подмножество ребер так, чтобы:
(F-sum(c)) / sum(t) >= X.

Немного пожонглируем слагаемыми:
X * sum(t) + sum(c) <= F

Далее думаю все очевидно. Взвесим ребра величинами X * t + c, и найдем минимальное остовное дерево. Если его вес <= F, значит (F-sum(c)) / sum(t) >= X, иначе - нет, и делаем соответствующий шаг в двоичном поиске.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Ещё одна задача на дерево интервалов... гость Задачи 5 09.11.2009 14:06
Задача про минимальное количество прямых,которыми можно покрыть точки гость Вычислительная геометрия 3 26.05.2009 17:48
второе минимальное остовное дерево sawe Реализация, исходники, языки 7 04.09.2008 19:15
минимальное стягивающее дерево по критерию максимальной живучести ТРСО andrew_zol Графы 0 21.06.2007 03:08
минимальное расстояние andy_84 Математические алгоритмы 3 16.12.2006 16:01