1 / 1 / 0
Регистрация: 14.07.2019
Сообщений: 43
1

Иннокентий и очень известная страна. Люди добрые, быстрей, пожалуйста

20.10.2019, 11:01. Показов 1027. Ответов 0
Метки нет (Все метки)

Задача C. Иннокентий и одна очень известная страна
Имя входного файла: input.txt
Имя выходного файла: output.txt
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт
Иннокентий работает в одной очень большой корпорации. Сейчас его заданием является откры-
тие филиала в новой стране. В стране N городов соединенных N − 1 дорогой так, что из любого
города можно добраться до любого другого.
Открытие филиала — дело ответственное. Филиал должен располагаться в городе, стоимость
транспортировки из которого минимальна. Для этого Иннокентий придумал следующую форму
расчета: пусть u — выбранный город, а vi — соседние города, то есть такие, в которые можно
попасть из
P
u, проехав ровно по одной дороге. Тогда стоимость транспортировки определяется как
(dvi + 1)2
, где dvi — длина наибольшего пути, начинающегося в городе vi
, который не проходит
дважды через какой-либо город и не проходит через u. Помогите Иннокентию выбрать город, в
котором нужно разместить склад, чтобы стоимость была минимальной.
Формат входных данных
В первой строке входного файла записано число N — количество городов (1 6 N 6 5 · 105
).
В следующих N − 1 строках дано описание дорог. Каждая строка содержит по два целых числа
u и v — номера городов, которые соответствующая дорога соединяет (1 6 u, v 6 N, u 6= v).
Формат выходных данных
В выходной файл необходимо вывести два числа: наименьшую стоимость размещения филиала
и город, при выборе которого она достигается. Если подходящих ответов несколько, выведите любой
из них.
Система оценки
Решения, правильно работающие для N 6 104
, будут оцениваться в 40 баллов.
Примеры
input.txt output.txt
4
1 2
2 3
2 4
3 2
2
1 2
1 1
__________________
Помощь в написании контрольных, курсовых и дипломных работ здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
20.10.2019, 11:01
Ответы с готовыми решениями:

Добрые люди! Очень нужна Ваша помощь!
У меня такая проблема. В 1С 7.7 Торговля+Склад нужно добавить колонку Штрих-кодов в справочник...

HELP пожалуйста люди добрые с DIPLADOKS !
помогите победить это ГМО , в автозагрузке появляется постоянно ! через regedit прохожу по пути там...

Программа на курсовой попалась очень сложная, выручайте люди добрые
Сумма долга 000177 Требуется определить современное значение долга, дисконтированную его сумму,...

Люди добрые нужно разобраться с запросами SQL пожалуйста!
1. Выбрать все книги, у которых прошел срок возврата. 2. Выбрать все книги, выпущенные...

0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
20.10.2019, 11:01

Задачки по PHP. Пожалуйста, люди добрые, до экзамена не допустят
1.Даны текстовые файлы f и g. Записать в файл h сначала компоненты файла f, затем - компоненты...

Добрые люди, скажите пожалуйста как выполняется перегрузка операторов
Помогите((( Я не понимаю, как нужно сделать перегрузку операторов * для умножения числа на вектор....

Если есть добрые люди, напишите пожалуйста блок-схему к вот этому коду!
Помогите пожалуйста uses crt; const ...

А сколько стоит заказать работу на паскале? Или может быть есть такие добрые люди, которые сделают бесплатно. Подскажите пожалуйста
P.S.: я новичок, поэтому не знаю, куда и к кому по этому вопросу обращаться. Простите, если что, за...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru