|
Название задачи: Выгодней некуда . |
 |
Условие
В стране 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, для которого средняя выручка за единицу времени
1. Существует цикл D положительного c'-веса. Это означает, что
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*, которое мы хотим получить.
