题解 P1396 【营救】
我来写一个题解
本来做这道题目是想练一练最短路的
可是我在做最短路的过程中发现这是一道
最小生成树
普及一下最小生成树的算法：
分为两种，一种是Prim，还有一种是Kruskal
这里使用Kruskal算法（比较方便）
下面是分析：
因为本题是求最短路中的最大值的最小值是多少
那么我们就可以求s到t的最短路中最小值中最大值是多少就可以了（有点绕人）
所以我就想到了完美的Kruskal算法
我们可以把求最小值的过程转化为跑一遍最小生成树的过程
那么也就把问题转化为：在一个无向图中，求其最小生成树中权值最大的一条边是多少。
也就是求一个图的最小瓶颈树
好了，问题转化完毕。
接下来是怎么实现
怎么求最小生成树的最大权（见洛谷OJ的P1547:Out of Hay）
那么怎么求最小生成树的最大权呢
很简单，我们只要在算最小生成树的时候保存一下当前的权与最大值的较大值就可以了
还有一件事
怎样求s到t的最小生成树呢（怎样判定s与t已经连接取最大值了呢？）
这个想一下就好了，因为Kruskal求生成树的过程是一点一点用并查集连接（并）的
所以在第一次s与t这两个点连接时所得到的最大权值即为所求
解释完美结束
下面是美丽的代码：
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=20001;
struct save {
int x,y,v;
} a[N];
int father[N];
int n,m,s,t,maxn=-0x7fffffff;
bool cmp(save m,save n) {
return m.v<n.v;
}
int find(int x) {
if(father[x]!=x)
father[x]=find(father[x]);//路径压缩
return father[x];
}
int main() {
int i;
cin>>n>>m>>s>>t;
for(i=1; i<=n; i++)
father[i]=i;
for(i=1; i<=m; i++)
cin>>a[i].x>>a[i].y>>a[i].v;
sort(a+1,a+m+1,cmp);//按照权值排下序
for(i=1; i<=m; i++) {
int t1,t2;
t1=find(a[i].x);
t2=find(a[i].y);
if(t1!=t2) {//如果不是一个祖先（需要连接）
father[t1]=t2;
if(find(s)==find(t)) {//如果s与t连接了
maxn=max(maxn,a[i].v);//保存最大值
break;//此时因为已经是答案了，所以直接跳出
}
else
maxn=max(maxn,a[i].v);//保存最大值
}
}
cout<<maxn<<endl;//输出最大值
return 0;
}