10pts,除#1全部MLE,使用了并查集
查看原帖
10pts,除#1全部MLE,使用了并查集
1066617
_ACGODs_楼主2024/11/19 20:09
#include<bits/stdc++.h>
using namespace std;
//#define Udebug//调试开关
int n,m;
struct edge{
	int u;
	int v;
	int val;
}lst[100010];
int enemy[100010],fa[100010];
bool cmp(edge a,edge b){
	return a.val>b.val;
}
int find(int a){
#ifdef Udebug
	cout<<a<<"find"<<fa[a]<<endl;
#endif
	if(a==fa[a]) return a;
	return (fa[a]=find(a));
}
bool check(int a,int b){
#ifdef Udebug
	cout<<a<<' '<<b<<endl;
#endif
	a=find(a);
	b=find(b);
	return a==b;
}
void add(int a,int b){//加边!
#ifdef Udebug
	cout<<a<<' '<<b<<endl;
#endif
	a=find(a);
	b=find(b);
	fa[a]=b;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>lst[i].u>>lst[i].v>>lst[i].val;
	}
	sort(lst+1,lst+m+1,cmp);
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=m;i++){
		int u=lst[i].u;
		int v=lst[i].v;
		if(check(u,v)){
			cout<<lst[i].val<<endl;
			return 0;
		}
		else{
			if(enemy[u]==0) enemy[u]=v;
			else add(v,enemy[u]);
			if(enemy[v]==0) enemy[v]=u;
			else add(u,enemy[v]);
		}
	}cout<<0<<endl;
	return 0;
}
2024/11/19 20:09
加载中...