AcWing 3245. 地铁修建
原题链接
中等
作者:
把这题Ac了
,
2024-12-01 13:46:57
,
所有人可见
,
阅读 1
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1e5 + 10,M = 2 * N;
int p[N]; //并查集查看是否在同一集合内
int n,m;
struct node {
int a,b,w;
//sort为 : sort(edge,edge + m);
bool operator< (const node& node)const {
return w < node.w;
}
}edge[M];
int find(int x){
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main(){
cin >> n >> m;
for(int i = 1;i <= n;i++) p[i] = i;
for(int i = 0;i < m;i++){
int a,b,w;
cin >> a >> b >> w;
edge[i] = {a,b,w};
}
sort(edge,edge + m);
queue<int> q;
int res = -1; // 用来判断最小生成树是否有n个结点
for(int i = 0;i < m;i++){
int a = edge[i].a,b = edge[i].b,w = edge[i].w;
int pa = find(a),pb = find(b);
if(pa != pb) {
p[pb] = pa;
if(find(1) == find(n)){
cout << w << endl;
break;
}
}
}
return 0;
}