李慕航 • 1天前
using namespace std;
struct edge{
long long u,v,w;
}e[2000005]; long long n,m,cnt=0,sum=0,f[2000005],ma=0; bool cmp(edge x,edge y){
return x.w<y.w;
} int find(int x) {
if (f[x] == x) {
return x;
}
int y = find(f[x]);
f[x] = y;
return y;
} int k(){
long long sum=0;
for(int i=1;i<=m;i++){
int u,v,w;
u=e[i].u;
v=e[i].v;
w=e[i].w;
if(find(u)==find(v)){
continue;
}else{
int a=find(u);
int b=find(v);
f[a]=b;
cnt++;
if(ma<w){
ma=w;
}
}
if(cnt==n-1){
break;
}
}
if(cnt!=n-1){
return -1;
}
return ma;
} int main() {
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>e[i].u>>e[i].v>>e[i].w;
}
for(int i=0;i<=n;i++){
f[i]=i;
}
sort(e+1,e+m+1,cmp);
int p=k();
if(p==-1){
cout<<"orz\n";
return 0;
}
cout<<p<<endl;
return 0;
}
评论:
请先登录,才能进行评论