NKRACING - Vòng đua F1
Tác giả: RR
Ngôn ngữ: Pascal
//Wishing myself a happy lunar new year with a lot of accept solutions
//Written by Nguyen Thanh Trung
{$R-,Q-}
const
FINP='';
FOUT='';
MAXN=10000;
MAXM=100000;
var
m,n,sum,mst:longint;
eu,ev,ec:array[1..MAXM] of longint;
father:array[1..MAXN] of longint;
procedure inp; inline;
var
f:text;
i:longint;
begin
assign(f,FINP); reset(f);
read(f,n,m);
for i:=1 to m do
read(f,eu[i],ev[i],ec[i]);
sum:=0;
for i:=1 to m do inc(sum,ec[i]);
close(f);
end;
procedure ans; inline;
var
f:text;
begin
assign(f,FOUT); rewrite(f);
writeln(f,sum-mst);
close(f);
end;
procedure swap(var a,b:longint); inline;
var
temp:longint;
begin
temp:=a; a:=b; b:=temp;
end;
procedure sort(l,r:longint); inline;
var
i,j,mid:longint;
begin
i:=l; j:=r; mid:=ec[i+random(j-i+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;
function getRoot(u:longint):longint; inline;
begin
if father[u]<0 then getRoot:=u
else begin father[u]:=getRoot(father[u]); getRoot:=father[u]; end;
end;
procedure union(r1,r2:longint); inline;
begin
if father[r1]<father[r2] then
begin
father[r1]:=father[r1]+father[r2];
father[r2]:=r1;
end
else
begin
father[r2]:=father[r1]+father[r2];
father[r1]:=r2;
end;
end;
procedure solve; inline;
var
i,sc,u,v,r1,r2:longint;
begin
for i:=1 to n do father[i]:=-1;
sort(1,m); sc:=0; mst:=0;
for i:=1 to m do
begin
u:=eu[i]; v:=ev[i];
r1:=getRoot(u);
r2:=getRoot(v);
if r1=r2 then continue;
union(r1,r2);
inc(sc); inc(mst,ec[i]);
if sc=n-1 then break;
end;
end;
begin
inp;
solve;
ans;
end.