并查集 60pts
查看原帖
并查集 60pts
112631
Lovable_Wind楼主2020/12/12 21:51
#include<bits/stdc++.h>
using namespace std;
const double pi=3.14;
const int inf=0x3f3f3f3f;
const int NIL=-1;
const int MAXN=100010;
#define f(i,l,r) for(int i=l;i<=r;i++)
struct qf{
	int a,b,v;
}p[MAXN];
int n,m,fa[100010];
int get(int x){
	if (fa[x]==x) return fa[x];
	return fa[x]=get(fa[x]);
}
bool jmerge(int x,int y){
	if (get(x)!=get(y)){
		fa[get(x)]=y;
		return 0;
	}
	return 1;
}
bool cmp1(qf x,qf y){
	if (x.v<=y.v) return 0;
	return 1; 
}
int read()
{
    int ans=0,flag=1;
    char ch=getchar();
    while( (ch>'9' || ch<'0') && ch!='-' ) ch=getchar();
    if(ch=='-') flag=-1,ch=getchar();
    while(ch>='0' && ch<='9') ans=ans*10+ch-'0',ch=getchar();
    return ans*flag;
}
int main()
{
	n=read(),m=read();
	f(i,1,n){
		fa[i]=i;
	}
	f(i,1,m){
		cin>>p[i].a>>p[i].b>>p[i].v;
	}
	sort(p+1,p+m+1,cmp1);
	f(i,1,m){
		if (jmerge(p[i].a,p[i].b)){
			cout<<p[i].v<<endl;
			return 0;
		}
	}
	cout<<0<<endl;
}
2020/12/12 21:51
加载中...