Задача«Алгоритм Прима»
Постановка задачи. Тимур и его друзья, приехав летом на свои старые дачи, решили устроить на время своего отдыха игру. Они организовали команду, чтобы тайно помогать жителям дачного городка в их повседневных делах.Дачный поселок довольно большой, и дома, в которых живут друзья Тимура, расположены далеко друг от друга. Как быстро передавать друг другусообщения? Как собирать ребят на совет?Тимур решил проложить веревочный телеграф, который связал бы все домики, в которых живут ребята из его команды. Всего домиков N. Покарте ребята вычислили координаты каждого домика (Хi, Yi) в целых числах и выписали их на бумаге. За единицу измерения координат они взяли один метр. Однако возник вопрос: какие домики нужно соединять веревочным телеграфом, чтобы связь была между всеми домиками (возможно, через другие домики), а общая длина всех веревок была как можно меньше?
Требуется написать программу, которая по координатам домиков определяла бы, какова минимальная общая длина всех веревок, соединяющих все домики между собой (возможно, через другие домики).
Достарыңызбен бөлісу: |
