Каранаев Линар Минтимерович Стерлибашево 2017 содержание глава реферативное изложение

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

0≤N≤100

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

begin

InputData; {Ввод исходных данных}

OutputData: {Вывод результата}

end.

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

procedure InputData;

begin

assign (mput,'input.txt');

readln(N);

for i:=l to N do readln(x[i],y[i]);

close(input);

for i:=l to N do

for j:=l to N do

D[1.j]:=sqrt(sqr(x[i]-x[j])*sqr(y[1]-y[j]));

end;

Ответ задачи по построенному остовному дереву получается следующим образом:

procedure OutputData:

var

begin

for i:=2 to N do

Answer:=Answer+D[i, Pred[i]];

assign (output,'output.txt');

rewrite(output);

writeln(Answer:0:2);

close(output);

end;

На каждом шаге в множество (дерево) А добавляется ребро наименьшего веса среди ребер, соединяющих вершины из дерева А с вершинами не из дерева А. После выполнения N - 1 раз таких добавлений мы получаем минимальное остовное дерево.

Для эффективной организации выбора нужного для добавления ребра используется очередь с приоритетами, в которой хранятся все вершины, еще не попавшие в дерево A. При этом каждая вершина i снабжена также приоритетом – специальной характеристикой Key[i], которая равна минимальному весу ребер, соединяющих вершину i с вершинами из А.

Более формально алгоритм Прима может быть записан следующим образом:

Ставим в очередь Q все вершины исходного графа

Устанавливаем для всех вершин Key[i] - бесконечность (MaxD)

Заносим в дерево А вершину 1:

key[l] = 0 – расстояние от нее до вершин дерева А

Pred[l] = 0 – у корневой вершины нет предка

Пока очередь Q не пуста

Выбираем из очереди вершину U такую, для которой расстояние

от нее до вершин из множества А минимально

Для каждой вершины V, соседней с U

(то есть в графе имеется ребро (U,V)).

если V находится в очереди и D[U,V]

то Pred[V]=U key[V]=D[U,V]

Ниже приведена реализация алгоритма Прима:

procedure MinTree;

Const

MaxD =le16; {бесконечность}

Used =1;

var

Lbl: array [l..MaxN] of byte;

U, v: byte;

Min: single;

begin

begin

Lbl[i]:=Free; { Всевершинывочереди}

end;

Key[l]:=0; { Начнем построение с остова с 1-й вершины}

for i:=l to N do { Длявсехвершин }

begin

Min:=MaxD;

if (Lbl[j]=Free) and (Key[j]

then begin u:=j; Min:=Key[j]; end;

Lbl[u]:=Used; { Помечаем ее как использованную}

forv:=ltoNdo { Для всех оставшихся в очереди вершин}

if (Lbl[v]=Free) and (D[u,v]

then

begin { Пересчитываем }

Pred[v]:=u; { Переустанавливаем предка}

end;

end;