poj 2395
用的是克鲁斯卡尔算法,跟2485差不多,也是求最小生成树中最长的一段
program poj2395;
type
node=record
x,y,c:longint;
end;
var
a:array[1..10000] of node;
father:array[1..2000] of integer;
n,m,i,k,ans:longint;
procedure quick(left,right:integer);
var
i,j,temp:longint;
p:node;
begin
i:=left;
j:=right;
temp:=a[(i+j) div 2].c;
while i<=j do
begin
while a[i].c<temp do inc(i);
while a[j].c>temp do dec(j);
if i<=j then
begin
p:=a[i];
a[i]:=a[j];
a[j]:=p;
inc(i);
dec(j);
end;
end;
if left<j then quick(left,j);
if i<right then quick(i,right);
end;
function getfather(num:integer):integer;
begin
if father[num]=num then getfather:=num
else
begin
father[num]:=getfather(father[num]);
getfather:=father[num];
end;
end;
begin
fillchar(a,sizeof(a),0);
readln(n,m);
for i:=1 to m do
readln(a[i].x,a[i].y,a[i].c);
quick(1,m);
for i:=1 to n do
father[i]:=i;
ans:=-maxlongint;
k:=0;
for i:=1 to m do
if getfather(a[i].x)<>getfather(a[i].y) then
begin
father[getfather(a[i].y)]:=getfather(a[i].x);
if ans<a[i].c then ans:=a[i].c;
inc(k);
if k=n-1 then break;
end;
writeln(ans);
end.