На этом шаге рассмотрим метод Крускала и его применение для решения ранее рассмотренной олимпиадной задачи.

    Для решения многих олимпиадных задач удобнее применять метод Крускала. Рассмотрим вначале его применение в для решения задачи "Веревочный телеграф&qot;.

    В тело главной программы внесено существенное изменение:

begin 
	InputData; 
	QuickSortR(1,N * (N - 1) div 2); 
	MinTree_Kruskal; 
	OutputData;
end. 

    Алгоритм Крускала работает на множестве упорядоченных по возрастанию весов ребер R[k]. Поэтому перед началом его работы необходимо произвести переупорядочивание ребер по возрастанию весов. Эту работу и выполняет рекурсивная процедура QuickSortR, которой при начальном вызове передаются номера начального (номер 1) и конечного (номер N(N - l)/2) ребер. В данном случае рекомендуется применять алгоритм быстрой сортировки.

    Ввод данных тоже приходится немного изменить.

procedure InputData;
begin  
  assign (input,'input.txt');
  reset(input);
  readln(N); 
  for  i := 1 to  N do 
    readln(x[i], y[i]);
  close(input); 
  k := 0;
  for  i := 1 to  N - 1 do  
    for  j := i + 1 to  N do  
	begin
		inc(k);
		R[i, j] := sqrt(sqr(x[i] - x[j]) + sqr(y[i] - y[j])); 
		B[k] := i;
		E[k] := j;
	end;
end;  

    Здесь граф представлен как набор из N(N -1)/2 ребер, где:

• R[k] — вес ребра (длина веревки) с номером k;
• B[k] — начальная вершина ребра;
• E[k] — конечная вершина ребра.

    Ответ будет накапливаться в переменной Answer непосредственно в процессе добавления ребер в минимальное остовное дерево, поэтому процедура вывода результата предельно упростится:

procedure  OutputData; 
begin  
  assign(output, 'output.txt'); 
  rewrite(output);
  writeln(Answer:0:2); 
  close(output); 
end;

    Процедура же построения минимального остовного дерева методом Крускала выглядит следующим образом:

procedure MinTree_Kruskal; 
begin 
   for i := 1 to N do 
      Makeset(i); 
   Answer := 0; 
   for i := 1 to k do 
      if FindSet(B[i]) <> FindSet(E[i]) then 
      begin 
         Answer := Answer + R[i]; 
         Union(B[i], E[i]); 
      end; 
end;

    На следующем шаге рассмотрим работу алгоритма Крускала.

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