讨论 / AC 100 纪念一下~~【pascal】
songyaoyang 2013-11-06 04:56:33
点我顶贴 收藏 删除
type

node=record x,y,w:longint; end;

var

e:array [0..100000] of node;

f:array [0..100000] of longint;

i,j,k,m,n,r1,r2,ans:longint;

procedure qsort(l,r:longint);

var

i,j:longint;

x:node;

begin

i:=l; j:=r;

x:=e[i];

while i<j do begin

while (i<j) and (e[j].w>=x.w) do dec(j);

e[i]:=e[j];

while (i<j) and (e[i].w<=x.w) do inc(i);

e[j]:=e[i];

end;

e[i]:=x;

if l<i-1 then qsort(l,i-1);

if j+1<r then qsort(j+1,r);

end;

function find(x:longint):longint;

begin

if f[x]=x then exit(x);

f[x]:=find(f[x]);

exit(f[x]);

end;

begin

readln(n,m);

for i:=1 to m do

with e[i] do

readln(x,y,w);

qsort(1,m);

for i:=1 to n do f[i]:=i;

ans:=0;

for i:=1 to m do begin

r1:=find(e[i].x);

r2:=find(e[i].y);

if r1<>r2 then begin f[r1]:=r2;inc(ans,e[i].w); end;

end;

writeln(ans);

end.

查看更多回复
提交回复