P1111 修复公路

​​传送门​​

思路：

用并查集来维护村与村之间的联通关系，类似于最小生成树中的并查集用法。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node{
  int u,v,t;
  friend bool operator < ( node a, node b)
  {
    return a.t > b.t;
  }
};
priority_queue<node>q;
int f[100010];
int find(int x)
{
  return f[x]==x?x:f[x]=find(f[x]);
}
node now;
int main()
{
  int n,m;
  cin>>n>>m;
  for(int i = 1; i <= n; i++)f[i] = i;
  while(m--)
  {
    int x,y,t;
    cin>>x>>y>>t;
    now.u = x;
    now.v = y;
    now.t = t;
    q.push(now);
  }
  int cnt = 0;
  while(!q.empty())
  {
    now = q.top();
    q.pop();
    if(f[find(now.u)] != find(now.v))
    {
      cnt++;
    }
    f[find(now.u)] = f[find(now.v)];
    if(cnt == n-1)
    {
      cout<<now.t;
      return 0;
    }
  }
  if(cnt < n-1)
  {
    cout<<"-1"<<endl;
  }
}