QBMST - Cây khung nhỏ nhất ( HEAP )
Tác giả: RR
Ngôn ngữ: Pascal
var
u,v,res,i,n,m:longint;
lab,eu,ev,ec:array[1..15111] of longint;
procedure swap(var a,b:longint);
var
tmp:longint;
begin
tmp:=a; a:=b; b:=tmp;
end;
procedure sort(l,r:longint);
var
i,j,mid:longint;
begin
i:=l; j:=r; mid:=ec[l+random(r-l+1)];
repeat
while ec[i]<mid do inc(i);
while ec[j]>mid do dec(j);
if i<=j then
begin
swap(eu[i],eu[j]);
swap(ev[i],ev[j]);
swap(ec[i],ec[j]);
inc(i); dec(j);
end;
until i>j;
if i<r then sort(i,r);
if l<j then sort(l,j);
end;
procedure union(r1,r2:longint);
var
x:longint;
begin
x:=lab[r1]+lab[r2];
if lab[r1]<lab[r2] then
begin
lab[r1]:=x;
lab[r2]:=r1;
end
else
begin
lab[r2]:=x;
lab[r1]:=r2;
end;
end;
function getRoot(u:longint):longint;
begin
if lab[u]<0 then exit(u);
lab[u]:=getRoot(lab[u]); exit(lab[u]);
end;
begin
read(n,m);
for i:=1 to m do
read(eu[i],ev[i],ec[i]);
sort(1,m);
for i:=1 to n do lab[i]:=-1;
for i:=1 to m do
begin
u:=getRoot(eu[i]);
v:=getRoot(ev[i]);
if u<>v then
begin
union(u,v);
inc(res,ec[i]);
end;
end;
writeln(res);
end.