Программирование на языке Pascal



         

Реализация


procedure step(v,k: byte; r: longint); var j: byte; begin if r < min then if k = N-1 then min:= r else for j:= 1 to N do if (sm[v,j]<>0)and(mark[j]=0) then begin mark[j]:= 1; step(j,k+1,r+sm[v,j]); mark[j]:= 0 end; end;

begin ... for i:= 1 to N do mark[i]:= 0; min:= MaxLongInt; for i:= 1 to N do begin mark[i]:=1; step(i,1,0); mark[i]:=0; end; writeln(min); ... end.

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




Содержание  Назад  Вперед