題目描述

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.

轉載于:https://www.cnblogs.com/YYC-0304/p/9499969.html

總結

以上是生活随笔為你收集整理的Out of Hay的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。