P1396 营救

​​传送门​​

思路：

克鲁斯卡尔最小生成树，在加入边的时候判断s与t是否已经连通即可。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int inf = 0x3f3f3f3f;
int f[10010];
int find(int x)
{
  return f[x] == x ? x : f[x]=find(f[x]);
}
struct node
{
  int x,y;
  int w;
  friend bool operator < (node a, node b)
  {
    return a.w > b.w;
  }
};
priority_queue<node>q;
node now;

int main()
{
  int n,m,s,t;
  cin>>n>>m>>s>>t;
  for(int i = 1; i <= n; i++)f[i] = i;
  while(m--)
  {
    int u,v,w;
    cin>>u>>v>>w;
    now.x = u;
    now.y = v;
    now.w = w;
    q.push(now);
  }
  int cnt = 0;
  int ans = 0;
  while(cnt < n)
  {
    now = q.top();
    q.pop();
    if(find(now.x) != find(now.y))
    {
      cnt++;
      f[find(now.x)] = find(now.y);
      ans = max(ans,now.w);
      if(find(s) == find(t))
      break;
    }
  }
  cout<<ans<<endl;
  return 0;
}