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

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

procedure InputData; 
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; 

    Результат работы алгоритма построения остовного дерева методом Прима будет представлен в виде массива Pred [1..N]: Pred [i] = j, то есть предком вершины i в остовном графе будет вершина j, или, другими словами, минимальное остовное дерево будет содержать ребро (i, j). У вершины 1 предка не будет (Pred[l] = 0).

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

procedure OutputData;
var 
	Answer : single; 
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; 

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

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