题目描述
“咚咚咚……”“查水表!”原来是查水表来了,现在哪里找这么热心上门的查表员啊!YYH感动的热泪盈眶,开起了门……
YYH的父亲下班回家,街坊邻居说YYH被一群陌生人强行押上了警车!YYH的父亲丰富的经验告诉他YYH被带到了t区,而自己在s区。
该市有m条大道连接n个区,一条大道将两个区相连接,每个大道有一个拥挤度。YYH的父亲虽然很着急,但是不愿意拥挤的人潮冲乱了他优雅的步伐。所以请你帮他规划一条从s至t的路线,使得经过道路的拥挤度最大值最小。
输入输出格式
输入格式:
第一行四个数字n,m,s,t。
接下来m行,每行三个数字,分别表示两个区和拥挤度。
(有可能两个区之间有多条大道相连。)
输出格式:
输出题目要求的拥挤度。
这道题目有2种做法:
1.kruskal
2.二分
对于第一种算法,我们知道最小的路一定在最小生成树上。这道题的原理可同NOIP货车运输
对于第二种算法,我们发现这道题的答案具有结论单调性,所以我们可以二分答案,然后用链表处理即可、。
下面贴第一种算法的代码
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,s,t;
struct edge{
int x,y,k;
}bian[];
int f[];
bool cmp(edge a,edge b){return a.k<b.k;}
int getfa(int x){return x==f[x]?x:f[x]=getfa(f[x]);}
int main(){
scanf("%d%d%d%d",&n,&m,&s,&t);
for(int i=;i<=m;i++)
scanf("%d%d%d",&bian[i].x,&bian[i].y,&bian[i].k);
sort(bian+,bian+m+,cmp);
for(int i=;i<=n;i++)
f[i]=i;
for(int i=;i<=m;i++)
{
int x=getfa(f[bian[i].x]),y=getfa(f[bian[i].y]);
if(x!=y)f[x]=y;
if(getfa(f[s])==getfa(f[t]))
{
printf("%d\n",bian[i].k);
break;
}
}
return ;
}