Сеть дорог
В некоторой стране 225 городов, из которых 15 — областные центры. Некоторые города соединены между собой дорогами (но не более чем одной для каждой пары городов), причем любой путь по дорогам между двумя обычными городами, если он есть, проходит хотя бы через один областной центр. Какое наибольшее количество дорог могло быть в этой стране?
В некоторой стране 225 городов, из которых 15 — областные центры. Некоторые города соединены между собой дорогами (но не более чем одной для каждой пары городов), причем любой путь по дорогам между двумя обычными городами, если он есть, проходит хотя бы через один областной центр. Какое наибольшее количество дорог могло быть в этой стране?
Answers & Comments
Verified answer
Вы сговорились, что ли? Восьмой раз одну и ту же задачу дают.Всего в стране 15 центров и 210 обычных городов.
Прямых дорог между обычными городами нет, все дороги через центры.
Максимальное количество дорог будет, если из каждого центра выходит
210 дорог к каждому из 210 городов, и еще 14 дорог к другим центрам.
Между 15 центрами будет 15*14/2 = 105 дорог.
Из центров к простым городам 15*210 = 3150 дорог.
Всего получается 3150 + 105 = 3255 дорог в стране.