Out of Hay

本文主要是介绍Out of Hay，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

Bessie 计划调查N (2 <= N <= 2,000)个农场的干草情况，它从1号农场出发。农场之间总共有M (1 <= M <= 10,000)条双向道路，所有道路的总长度不超过1,000,000,000。有些农场之间存在着多条道路，所有的农场之间都是连通的。

Bessie希望计算出该图中最小生成树中的最长边的长度。

输入输出格式

输入格式：
两个整数N和M。

接下来M行，每行三个用空格隔开的整数A_i， B_i和L_i，表示A_i和 B_i之间有一条道路长度为L_i。

输出格式：
一个整数，表示最小生成树中的最长边的长度。

输入输出样例

输入样例#1：
3 3
1 2 23
2 3 1000
1 3 43
输出样例#1：
43
.
.
.
.
.
.

分析

只要生成最小生成树再扫一遍就可以了。
.
.
.
.
.
.

程序：

var
i,j,k,sum,ans,n,m:longint;
f:array[1..2000] of longint;
a,b,l:array[1..10000] of longint;
procedure sort(x,y:longint);  
var  
z,i,j,mid:longint;
begin   i:=x;j:=y;mid:=l[(x+y) div 2];repeatwhile l[i]<mid do inc(i);while l[j]>mid do dec(j);if not(i>j) thenbeginz:=l[i];l[i]:=l[j];l[j]:=z;z:=a[i];a[i]:=a[j];a[j]:=z;z:=b[i];b[i]:=b[j];b[j]:=z;inc(i);dec(j);end;until i>j;sort(x,j);sort(i,y);
end;
function find(x:longint):longint;
beginif f[x]=x then exit(x);f[x]:=find(f[x]);exit(f[x]);
end;
beginreadln(n,m);for i:=1 to m doreadln(a[i],b[i],l[i]);sort(1,m);j:=1;ans:=0;for i:=1 to n dof[i]:=i;for i:=1 to n-1 dobeginwhile f[find(a[j])]=find(b[j])do inc(j);f[find(a[j])]:=find(b[j]);if ans<l[j] then ans:=l[j];end;writeln(ans);  
end.

这篇关于Out of Hay的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---