一道pascal编程题

描述
A地区在地震过后，连接所有村庄的公路都造成了损坏而无法通车。政府派人修复这些公路。
给出A地区的村庄数N，和公路数M，公路是双向的。并告诉你每条公路的连着哪两个村庄，并告诉你什么时候能修完这条公路。问最早什么时候任意两个村庄能够通车，即最早什么时候任意两条村庄都存在至少一条修复完成的道路（可以由多条公路连成一条道路）
【数据规模】
N<=1000，M<=100000，x<=N，y<=N，t<=100000

输入格式(repair.in)
第1行两个正整数N，M
下面M行，每行3个正整数x, y, t，告诉你这条公路连着x,y两个村庄，在时间t时能修复完成这条公路。

输出格式(repair.out)
仅包含一行，如果全部公路修复完毕仍然存在两个村庄无法通车，则输出-1，否则输出最早什么时候任意两个村庄能够通车。

输入样例
4 4
1 2 6
1 3 4
1 4 5
4 2 3

输出样例
5

先按时间排序，每次连边再用并查集判断，下附程序（打得有点匆忙，有错的话请见谅）
var
i,j,k,n,m,bj:longint;
fa:array[1..1010]of longint;
x,y,t:array[1..101000]of longint;
Procedure qsort(l,r:longint);
var
i,j,mid:longint;
begin
i:=l; j:=r; mid:=t[(l+r)div 2];
repeat
while t[i]<mid do inc(i);
while t[j]>mid do dec(j);
if i<=j then
begin
k:=t[i];t[i]:=t[j]; t[j]:=k;
k:=x[i];x[i]:=x[j]; x[j]:=k;
k:=y[i];y[i]:=y[j]; y[j]:=k;
inc(i);dec(j);
end;
until i>j;
if i<r then qsort(i,r);
if l<j then qsort(l,j);
end;

Function findfa(x:longint):longint;
begin
if fa[x]=x then exit(x)
else
begin
findfa:=findfa(fa[x]);
fa[x]:=findfa;
end;
end;

begin

read(n,m);
for i:=1 to m do
read(x[i],y[i],t[i]);
for i:=1 to n do fa[i]:=i;
qsort(1,m);
for i:=1 to m do
begin
fa[findfa(x[i])]:=findfa(y[i]);
k:=findfa(1); bj:=1;
for j:=1 to n do if findfa(j)<>k then begin bj:=0; break;end;
if bj=1 then
begin
writeln(t[i]);
halt;
end;
end;
writeln('-1');
end.

温馨提示：内容为网友见解，仅供参考

当前网址：https://11.t2y.org/zz/ppsvq74fm.html