NKRACING - Vòng đua F1
Tác giả: ll931110
Ngôn ngữ: Pascal
{$MODE DELPHI}
program NKRACING;
const
input = '';
output = '';
maxn = 10000;
maxe = 1000000;
var
n,e: integer;
u,v,cost: array[1..maxe] of integer;
pr,rank: array[1..maxn] of integer;
tot,tree: integer;
procedure init;
var
f: text;
i: integer;
begin
assign(f, input);
reset(f);
readln(f, n, e);
tot := 0;
for i := 1 to e do
begin
readln(f, u[i], v[i], cost[i]);
tot := tot + cost[i];
end;
close(f);
end;
procedure sw(var x,y: integer);
var
z: integer;
begin
z := x; x := y; y := z;
end;
procedure swap(i,j: integer);
begin
sw(u[i],u[j]); sw(v[i],v[j]); sw(cost[i],cost[j]);
end;
procedure sort(l,h: integer);
var
i,j,p: integer;
begin
if l >= h then exit;
i := l; j := h; p := cost[random(h - l + 1) + l];
repeat
while cost[i] > p do inc(i);
while cost[j] < p do dec(j);
if i <= j then
begin
if i < j then swap(i,j);
inc(i); dec(j);
end;
until i > j;
sort(l,j); sort(i,h);
end;
function root(x: integer): integer;
begin
if x <> pr[x] then pr[x] := root(pr[x]);
root := pr[x];
end;
procedure link(x,y: integer);
begin
if rank[x] > rank[y] then pr[y] := x else pr[x] := y;
if rank[x] = rank[y] then inc(rank[y]);
end;
procedure solve;
var
i,nedge: integer;
begin
tree := 0;
for i := 1 to n do
begin
pr[i] := i;
rank[i] := 0;
end;
nedge := 0;
for i := 1 to e do
if root(u[i]) <> root(v[i]) then
begin
tree := tree + cost[i];
inc(nedge);
link(root(u[i]),root(v[i]));
end;
end;
procedure printresult;
var
f: text;
begin
assign(f, output);
rewrite(f);
writeln(f, tot - tree);
close(f);
end;
begin
init;
sort(1,e);
solve;
printresult;
end.