Задача 102893

Тема:    [ Двоичный поиск ]

Сложность: 3 Классы: Название задачи: Выгодней некуда .

Условие

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

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

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

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

Пример входного файла
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*. Возьмем некоторое пробное значение z₀ и рассмотрим граф с модифицированными весами [Кристофидес 78, п. 8.4]  с'_ij = c_ij - z₀b_ij. Используем алгоритм Флойда для нахождения циклов положительного c'-веса [Кристофидес 78, п. 8.4]. Возможны три случая.
1. Существует цикл D положительного c'-веса. Это означает, что откуда z₀ < z(D) ≤ z*.
2. Существует цикл D с нулевым (но не положительным) c'-весом. В этом случае

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

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

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

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

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