80分tle
查看原帖
80分tle
540066
zwb3_1415926楼主2023/10/17 20:59
#include<bits/stdc++.h>
using namespace std;
int n,m,pre[30000],b[30000];
struct g{int a,b,c;}l[100050];
bool cmp(g a,g b){return a.c>b.c;}
int f(int root)
{
	int fa=root,p;
	while (pre[fa]!=fa) fa=pre[fa];
	while (root!=fa)
	{
		p=pre[root];
		pre[root]=fa;
		root=p;
	}
	return fa;
}
void join(int a,int b)
{
	int r1=f(a),r2=f(b);
	if (r1!=r2) pre[r1]=r2;
}
bool check(int a,int b)
{
	int r1=f(a),r2=f(b);
	if (r1==r2) return true;
	else return false; 
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++) scanf("%d%d%d",&l[i].a,&l[i].b,&l[i].c);
	for (int i=1;i<=m;i++) pre[i]=i;
	sort(l+1,l+m+1,cmp);
	for(int i=1;i<=m+1;i++)
	{
		if (check(l[i].a,l[i].b)) {cout<<l[i].c;return 0;}
		else
		{
			if(!b[l[i].a]) b[l[i].a]=l[i].b;
			else join(b[l[i].a],l[i].b);
			if(!b[l[i].b]) b[l[i].b]=l[i].a;
			else join(b[l[i].b],l[i].a);
		}
	}
	return 0;
} 
2023/10/17 20:59
加载中...