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

   Решение

Докажите, что в любом треугольнике сумма медиан больше 3/4 периметра, но меньше периметра.

   Решение

Разрежьте фигуру, изображённую на рисунке, на две части, из которых можно сложить треугольник.

   Решение

Страница: << 1 2 [Всего задач: 7]      

По шоссе со скоростью 60 км/ч едет колонна машин длиной 300 м. Проезжая мимо поста ДПС, каждая машина сбрасывает скорость до 40 км/ч. БикЮ Какова будет длина колонны, когда все машины проедут пост ДПС?

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

Решение

В треугольнике ABC  ∠A = 40°,  ∠B = 20°,  а  AB – BC = 4.  Найдите длину биссектрисы угла C.

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

Решение

Страница: << 1 2 [Всего задач: 7]