有几个点不开O2mle,开了O2tle,求助大佬
查看原帖
有几个点不开O2mle,开了O2tle,求助大佬
800586
Woods_4325楼主2022/11/6 09:09
#include<cstdio> 
#include<algorithm>
using namespace std;
#define maxn 20010
#define maxm 100100
int n,m,enm[maxn],head[maxn];

struct type{
	int a,b,w;
	void in(int _a,int _b,int _w){
		a=_a,b=_b;w=_w;
	}
}f[maxm];

inline int read(){
	int i=0;
	int j=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-'){
			j=-1;
		}
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		i=i*10+ch-'0';
		ch=getchar();
	} 
	return i*j;
}

inline int find(int p){
    return p==head[p]?head[p]:find(head[p]);
}

bool cmp(type a,type b){
	return a.w>b.w;
}


int main(){
	n=read(),m=read();
	for(int i=1;i<=n;i++){
		head[i]=i;
	}
	for(int i=1;i<=m;i++){
		int a=read(),b=read(),c=read();
		f[i].in(a,b,c);
	}
	sort(f+1,f+1+m,cmp);
	for(int i=1;i<=m;i++){
		int a=f[i].a,b=f[i].b;
		int t=find(a),p=find(b);
		if(t==p){
			printf("%d",f[i].w);
			return 0;
		}
		head[a]=t;
		head[b]=p;
		if(enm[a]==0){
			enm[a]=b;
		}
		else{
			head[p]=enm[a];
		}
		
		if(enm[b]==0){
			enm[b]=a;
		}
		else{
			head[t]=enm[b];
		}
	}
	printf("0");
	return 0;
}
2022/11/6 09:09
加载中...