На этом шаге рассмотрим формулировку олимпиадной задачи, которая сводится к нахождению минимального остовного дерева.

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

    где X.xx — минимальная общая длина веревки с точностью до двух знаков в дробной части.

    Ограничения:
      0 < W < 100
      -32 000 < Xi, Yi < 32 000

    Рассмотрим домики тимуровцев как вершины графа, веревки между ними — как ребра графа, а длины веревок — как веса ребер. Теперь перед нами задача о минимальном остовном дереве. Тело программы, решающей эту задачу, может выглядеть следующим образом:

begin 
 InputData; {Ввод исходных данных} 
 MinTree; {Построение минимального остовного дерева}  
 OutputData; {Вывод результата}  
end. 

    В данном случае исходный граф — полный, то есть существует ребро между любыми его двумя вершинами, поскольку по условиям задачи веревки можно протянуть между любыми двумя домиками.

    На следующем шаге рассмотрим решение поставленной задачи.

Предыдущий шаг Содержание Следующий шаг