| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Kruskal算法解2395刷新纪录,用时0MS,求点击,附PASCAL代码program poj2395;
type
node=record
fromv,endv:integer;
weight:longint;
end;
var
e:array[1..10000] of node;
s:array[1..2000] of integer;
n,m,i,j,k,sum:longint;
procedure quick(h,r:integer);
var
i,j:integer;
x,t:longint;
begin
i:=h;j:=r;x:=e[(i+j)div 2].weight;
while i<j do
begin
while e[i].weight<x do inc(i);
while e[j].weight>x do dec(j);
if i<=j then
begin
t:=e[i].weight; e[i].weight:=e[j].weight; e[j].weight:=t;
t:=e[i].fromv; e[i].fromv:=e[j].fromv; e[j].fromv:=t;
t:=e[i].endv; e[i].endv:=e[j].endv; e[j].endv:=t;
inc(i);
dec(j);
end;
end;
if i<r then quick(i,r);
if j>h then quick(h,j);
end;
function find(v:integer):integer;
begin
if s[v]=v then find:=v
else
begin
s[v]:=find(s[v]);
find:=s[v];
end;
end;
begin
readln(n,m);
for i:=1 to m do
readln(e[i].fromv,e[i].endv,e[i].weight);
quick(1,m);
for i:=1 to n do s[i]:=i;
i:=1;
j:=1;
sum:=0;
while i<=n-1 do
begin
if find(e[j].fromv)<>find(e[j].endv) then
begin
s[find(e[j].fromv)]:=find(e[j].endv);
inc(i);
if e[j].weight>sum then sum:=e[j].weight;
end;
inc(j);
end;
writeln(sum);
end.
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator