題目描述

“咚咚咚……”“查水表！”原來是查水表來了，現在哪里找這么熱心上門的查表員啊！小明感動的熱淚盈眶，開起了門……

媽媽下班回家，街坊鄰居說小明被一群陌生人強行押上了警車！媽媽豐富的經驗告訴她小明被帶到了t區，而自己在s區。

該市有m條大道連接n個區，一條大道將兩個區相連接，每個大道有一個擁擠度。小明的媽媽雖然很著急，但是不愿意擁擠的人潮沖亂了她優雅的步伐。所以請你幫她規劃一條從s至t的路線，使得經過道路的擁擠度最大值最小。

輸入輸出格式

輸入格式：

?

第一行四個數字n，m，s，t。

接下來m行，每行三個數字，分別表示兩個區和擁擠度。

（有可能兩個區之間有多條大道相連。)

?

輸出格式：

?

輸出題目要求的擁擠度。

?

輸入輸出樣例

輸入樣例#1：
3 3 1 3 1 2 2 2 3 1 1 3 3 輸出樣例#1：
2

說明

數據范圍

30% n<=10

60% n<=100

100% n<=10000,m<=2n，擁擠度<=10000

題目保證1<=s,t<=n且s<>t，保證可以從s區出發到t區。

樣例解釋：

小明的媽媽要從1號點去3號點，最優路線為1->2->3。

?

/* MST 最小瓶頸生成樹 加邊的時候枚舉最大值就好了。 */#include <cstdio> #include <algorithm>using namespace std; class point { public:int x,y,v; }; int k,ans; point p[100001]; int father[100001]; int find(int x) {if(x!=father[x])find(father[x]);else return father[x]; } void unionn(int x,int y) {x=find(x);y=find(y);if(x!=y)father[x]=y; } bool cmp(const point &a,const point &b) {return a.v<b.v; } int main() {int n,m,s,t;scanf("%d%d%d%d",&n,&m,&s,&t);for(int i=1;i<=m;i++)scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].v);for(int i=1;i<=n;i++)father[i]=i; sort(p+1,p+m+1,cmp);for(int i=1;i<=m;i++){if(find(p[i].x)!=find(p[i].y)){k++;unionn(p[i].x,p[i].y);ans=max(ans,p[i].v); }if(find(s)==find(t))break;if(k==n-1)break;}printf("%d",ans);return 0; }

?

轉載于:https://www.cnblogs.com/L-Memory/p/6362844.html

總結

以上是生活随笔為你收集整理的洛谷P1396营救（最小生成树）的全部內容，希望文章能夠幫你解決所遇到的問題。

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