QBMST - Cây khung nhỏ nhất ( HEAP )

Tác giả: flashmt

Ngôn ngữ: Pascal

var n,m,i,j,x,y,re:longint;
    a,b,c,d:array[1..15555] of longint;

procedure sort(l,r:longint);
var i,j,x,y:longint;
begin
     i:=l; j:=r; x:=c[(i+j) shr 1];
     repeat
           while c[i]<x do i:=i+1;
           while c[j]>x do j:=j-1;
           if i<=j then
           begin
                y:=a[i]; a[i]:=a[j]; a[j]:=y;
                y:=b[i]; b[i]:=b[j]; b[j]:=y;
                y:=c[i]; c[i]:=c[j]; c[j]:=y;
                i:=i+1; j:=j-1;
           end;
     until i>j;
     if i<r then sort(i,r);
     if l<j then sort(l,j);
end;

function find(x:longint):longint;
begin
     if x<>d[x] then d[x]:=find(d[x]);
     exit(d[x]);
end;

begin
     read(n,m);
     for i:=1 to n do d[i]:=i;
     for i:=1 to m do read(a[i],b[i],c[i]);
     sort(1,m);
     for i:=1 to m do
     begin
          x:=find(a[i]); y:=find(b[i]);
          if x<>y then
          begin
               d[y]:=x;
               dec(n); re:=re+c[i];
               if n=1 then
               begin
                    writeln(re); halt;
               end;
          end;
     end;
end.

Download