ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Чемпионат Урала 2006

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

I. Сеть портшлюзов

Ограничение времени: 4.0 секунды
Ограничение памяти: 64 МБ
Одна маггловская фирма предложила Люциусу Малфою заключить контракт на прокладку сети портшлюзов между филиалами фирмы. Магглы наивно полагают, что себестоимость портшлюза зависит от расстояния, на которое тот переносит, и готовы заплатить за каждый метр проложенной сети. Единственное их требование — чтобы с помощью этих портшлюзов можно было добраться от каждого филиала к каждому, и чтобы не было лишних портшлюзов (то есть, чтобы не существовало портшлюзов, которые можно было бы убрать с сохранением условия связности всех филиалов).
Люциус понимает, что себестоимость портшлюза определяют совсем другие факторы. Он хочет надуть магглов и сделать такой проект сети, при котором отношение суммарной себестоимости портшлюзов к той сумме, которую заплатят магглы, оказалось бы минимальным. Таким образом, он стремится минимизировать среднюю себестоимость одного метра сети. Помогите Люциусу надуть магглов.

Исходные данные

В первой строке входа находится число N (1 ≤ N ≤ 1000) — количество филиалов. Во второй строке находится число M (1 ≤ M ≤ 500000) — количество пар филиалов, между которыми технически возможно создать портшлюз. В следующих M строках идет описание каждой пары: через пробел выписаны номера филиалов, которые можно соединить, расстояние между ними в метрах, и себестоимость прокладки портшлюза. Себестоимость и расстояние — целые числа от 1 до 106. Можно считать, что какую-то сеть портшлюзов, удовлетворяющую условиям заказчика, всегда можно построить. Для любой пары филиалов есть не более одного способа соединения. По условиям контракта нельзя соединять филиал с самим собой.

Результат

Вывести минимальную среднюю стоимость одного метра сети с точностью до 10−8. Средняя стоимость одного метра равна отношению суммарной себестоимости к суммарной длине сети.

Примеры

исходные данныерезультат
3
3
1 2 50 60
1 3 100 100
2 3 100 100
1
3
3
1 2 1000 3000
1 3 1 5
2 3 1000 1997
2
Автор задачи: Автор — Ден Расковалов, текст — Станислав Васильев
Источник задачи: X командный Чемпионат Урала по спортивному программированию, 24-25 марта 2006 года
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1447. Сеть портшлюзов