ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 102893
Тема:    [ Двоичный поиск ]
Сложность: 3
Классы:
Название задачи: Выгодней некуда .
В корзину
Прислать комментарий

Условие

В стране N городов, в каждом из которых есть аэропорт. Авиакомпания, занимающаяся перевозкой грузов, имеет самолет и желает максимально выгодно его использовать. Для некоторых пар городов (A, B) известны время перелета из A в B и сумма выручки за доставку груза из A в B. Напишите программу, которая по этим данным находит для самолета замкнутый путь, максимизирующий среднюю выручку за единицу времени.

Считается, что самолет может вместить не более одного груза, а временем стоянки самолета в аэропорту следует пренебречь.

Входные данные

В первой строке входного файла содержится число городов N (1 ≤ N ≤ 100) и число возможных прямых рейсов M. В каждой из следующих M строк записана четверка чисел (i, j, bij, cij), описывающая возможный рейс между городами i и j со временем перелета bij и выручкой cij . Время перелета и выручка – положительные вещественные числа.

Выходные данные

В первой строке выходного файла должна содержаться максимальная средняя выручка за единицу времени, а во второй – замкнутый маршрут, заданный номерами своих вершин в порядке следования, на котором эта максимальная выручка достигается. Первая и последняя вершины маршрута должны совпадать. Входные данные будут таковы, что решение заведомо будет существовать.

Пример входного файла

3 3
1 2 1.0 2.0
2 3 1.0 2.0
3 1 2.0 1.0

Пример выходного файла

1.25
1 2 3 1

Решение

Скачать архив тестов и решений

Нужно найти такой цикл D, для которого средняя выручка за единицу времени максимальна (сумма берется по всем ориентированным ребрам цикла). Обозначим это максимальное значение через z*. Возьмем некоторое пробное значение z0 и рассмотрим граф с модифицированными весами [Кристофидес 78, п. 8.4]  с'ij = cij - z0bij. Используем алгоритм Флойда для нахождения циклов положительного c'-веса [Кристофидес 78, п. 8.4]. Возможны три случая.
1. Существует цикл D положительного c'-веса. Это означает, что откуда z0 < z(D) ≤ z*.
2. Существует цикл D с нулевым (но не положительным) c'-весом. В этом случае


откуда z0 = z(D) и z0 ≥ z(E) для любого другого цикла E. Следовательно, z0 = z*.
3. Все циклы графа имеют отрицательный c'-вес. Тогда для любого цикла D выполняются неравенства 

и z0 > z(D). Значит, z0 > z*.

Искать величину z* будем следующим образом. Сначала найдем для нее верхнюю (z1) и нижнюю (z2 ≥ z1 / 2) границы (подумайте, как это сделать!). Далее используем двоичный поиск, деля каждый раз отрезок [z1, z2] пробной точкой z0 = (z1 + z2) / 2 на две равные части и оставляя ту из них, на которой лежит z*. Необходимое при этом количество итераций пропорционально числу правильных значащих разрядов z*, которое мы хотим получить.

Источники и прецеденты использования

книга
предмет информатика
Автор Беров В., Лапунов А., Матюхин В., Пономарев А.
Название Особенности национальных задач по информатике
Издательство Триада-С
Год издания 2000
глава
Номер 3
Название Алгоритмы на графах
Задача
Номер 10

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .