求助,只过了一个样例!
查看原帖
求助,只过了一个样例!
798787
lxclxc6楼主2022/12/7 23:28

#include<bits/stdc++.h>
using namespace std;
#define N 20000000
int a[N],b[N];
struct node{
	int u,v,w;
}edge[20000000];
bool cmp(node a,node b){
	return a.w>b.w;
}
int find(int x){
	if(a[x]==x)
	return a[x];
	return a[x]=find(a[x]);
}
void merge(int x,int y){
	a[find(x)]=a[find(y)];
	return;
}
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=0;i<n;i++){
		a[i]=i;
	}
	for(int i=0;i<n;i++)
	cin>>edge[i].u>>edge[i].v>>edge[i].w;
	sort(edge,edge+m,cmp);
	for(int i=0;i<m;++i){
		int u=edge[i].u,v=edge[i].v,w=edge[i].w;
		int t1=find(u),t2=find(v);
		if(t1==t2){
			cout<<w;
			return 0;
		}
		else{
			if(!b[u]){
				b[u]=v;
			}
			else merge(b[u],v);
			if(!b[v]){
				b[v]=u;
			}
			else merge(b[v],u);
		} 
	}
	cout<<"0";
	return 0;
}
2022/12/7 23:28
加载中...