На этом шаге рассмотрим пояснения к задаче "Secret Pipes".

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

procedure inputdata;
var i,j:integer;
 begin
  assign (input,'input. txt'); reset(input);
  readln(n,p);
  for i:=1 to p do
    readln(b[i],e[i],r[i]);
  close(input);
 end;

    Теперь решение задачи можно обеспечить следующим образом:

1. Найдем минимальное остовное дерево.
2. "Удаляя" в цикле по очереди одно из найденных ребер минимального остовного дерева и достраивая оставшийся нецельным остов до минимального остовного дерева, вычисляем стоимости получающихся деревьев и запоминаем меньшую.

    Для нахождения минимального остовного дерева используем алгоритм Крускала:

procedure mintree_kruskal_1;
var i : integer;
begin 
 answer:=0; j:=0;
 for i:=1 to n do makeset(i);
 i:=1; 
 while j <> n-1 do 
 begin 
    if findset(B[i]) &t;> findSet(E[i]) then 
    begin 
       answer:= answer+r[i]; 
       inc(j); Key[j]:=i; 
       Union(B[i],E[i]);
    end; 
    inc(i); 
  end; 
end;

    Легко заметить, что в процедуру поиска минимального остовного дерева вместо строки увеличения ответа Answer := Answer + R[i] введена строка inc(j); Key[j]:=i;, которая сохраняет в массиве Кеу номера всех ребер, включенных в минимальное остовное дерево.

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

begin 
  InputData;
  QuickSortR(1,P);
  MinTree_Kruskal_1;
  for i:=1 to P do NotMasked[i]:=true;
  CurAnswer:=maxlongInt; MinAnswer:=Answer;
  for v:=1 to N-1 do 
      begin 
        NotMasked[key[v]]:=false; Answer:=MinAnswer-R[key[v]];
        for  i:=1 to  N do  Makeset(i);
        for  u:=1 to  N-1 do  
        if  NotMasked[key[u]] 
        then  
           begin  
               Union(B[key[u]],E[key[u]]);
              NotMasked[key[u]]:=false;
           end ; 
      i:=key[v]+1; j:=N-2;
      MinTree_Kruska1_2; 
      if Answer < CurAnswer then CurAnswer:=Answer;
      for u:=1 to N-1 do NotMasked[key[u]]:=true; 
    end; 
  assign (output,'secret.out'); rewrite(output);
  writeln(CurAnswer);
  close(output);
end.

    Здесь первые три строки

InputData;
  QuickSortR(1,P);
  MinTree_Kruskal_1; 

 for i:=1 to P do NotMasked[i]:=true;

    и инициализируем поиск минимального ответа:

CurAnswer:=maxlongInt;

    Далее в цикле по всем ребрам, включенным в минимальное остовное дерево,

 for v:=1 to N-1 do  

    помечаем текущее ребро минимального остовного дерева как занятое,

NotMasked[key[v]]:=false; 

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

    Среди получемых ответов Answer минимальный.

if Answer < CurAnswer then CurAnswer:=Answer;

    В конце цикла возвращаем "исключенное" ребро в список.

NotMasked[key[v]]:=true;

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

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