На этом шаге рассмотрим реализацию поставленной на преыдущих шагах задачи.
Архив с примером можно взять здесь.
program pr; Const MaxN = 100; var N, i, j : 1..MaxN; X, Y : array [1..MaxN] of longint; D : array [1..MaxN,1..MaxN] of single; Pred : array [1..MaxN] of byte; procedure InputData; var i, j : 1..MaxN; begin assign (input,'input.txt'); reset(input); readln(N); for i := 1 to N do readln(x[i],y[i]); close(input); for i := 1 to N do for j := 1 to N do D[i, j] := sqrt(sqr(x[i] - x[j]) + sqr(y[i] - y[j])); end; procedure OutputData; var Answer : single; i, j : 1..MaxN; begin Answer := 0; 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; procedure MinTree; Const MaxD = 1e16; {"бесконечность"} Free = 0; Used = 1; var Lbl : array [1..MaxN] of byte; Key : array [1..MaxN] of single; u, v : byte; Min : single; begin for i := 1 to N do begin key[i] := MaxD; Lbl[i] := Free; { Все вершины в очереди} end; Key[1] := 0; { Начнем построение с остова с 1-й вершины} Pred[1] := 0; { У 1-й вершины нет предка} for i := 1 to N do { Для всех вершин } begin Min := MaxD; for j := 1 to N do { Находим вершину, } if (Lbl[j] = Free) and (Key[j] < Min) then { ближайшую к остову } begin u := j; Min := Key[j]; end; Lbl[u] := Used; { Помечаем ее как использованную} for v := 1 to N do { Для всех оставшихся в очереди вершин} if (Lbl[v] = Free) and (D[u, v] < Key[v]) then begin { Пересчитываем } Key[v] := D[u, v]; { расстояние до растущего остова } Pred[v] := u; { Переустанавливаем предка} end; end; end; begin InputData; MinTree; OutputData; end.
На следующем шаге рассмотрим алгоритм Крускала.