P1396 营救

P1396 营救

luogu

解法：Kruskal最小生成树；
在构建最小生成树时，如果 s 与 t 在一个集合里时，当前边就是答案（因为便是按照升序排的）

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<vector>
using namespace std;
struct H{int x,y;int cost;
}a[20009];
int f[20009];
int find(int x)
{if(f[x]==x) return x;return f[x]=find(f[x]);
}
int s,t,n,m,ans;
int my_comp(const H&a,const H&b)
{if(a.cost<b.cost) return 1;return 0;
}
int main()
{scanf("%d%d%d%d",&n,&m,&s,&t);for(int i=1;i<=m;i++){int x,y,z;scanf("%d%d%d",&x,&y,&z);a[i].x=x,a[i].y=y,a[i].cost=z;}   for(int i=1;i<=n;i++) f[i]=i;sort(a+1,a+m+1,my_comp);for(int p=1;p<=m;p++){int c=find(a[p].x),b=find(a[p].y);f[c]=b;  if(find(s)==find(t)) {ans=a[p].cost;break;  }}printf("%d",ans);return 0;
}