В стране 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

   Решение

Страница: 1 2 3 4 5 6 7 >> [Всего задач: 59]      

Потроить треугольник по стороне c, медиане к стороне a m_a и медиане к стороне b m_b.

Прислать комментарий

Решение

Потроить треугольник по стороне a, стороне b и высоте к стороне a h_a.

Прислать комментарий

Решение

Hа доске была нарисована система координат и отмечены точки  A(1, 2)  и  B(3, 1).  Cистему координат стерли.
Bосстановите ее по двум отмеченным точкам.

Прислать комментарий

Решение

Потроить треугольник по высоте к стороне b h_b, высоте к стороне c h_c и медиане к стороне a m_a.

Прислать комментарий

Решение

Потроить треугольник по A, высоте к стороне b h_b и высоте к стороне c h_c.

Прислать комментарий

Решение

Страница: 1 2 3 4 5 6 7 >> [Всего задач: 59]