求助 P1525 为什么只有十分
  • 板块题目总版
  • 楼主hnoi
  • 当前回复0
  • 已保存回复0
  • 发布时间2022/11/6 12:02
  • 上次更新2023/10/27 04:04:50
查看原帖
求助 P1525 为什么只有十分
601142
hnoi楼主2022/11/6 12:02
#include<bits/stdc++.h>
using namespace std;
struct pri{
	int x;
	int y;
	int dis;
}a[200050];
bool cmp(pri a,pri b){
	return a.dis>b.dis;
}
int fa[20005],b[20005];
int get(int x){
	if(fa[x]==x) return x;
	fa[x]=get(fa[x]);
	return fa[x];
}
void hb(int p,int q){
	int x=get(p);
	int y=get(q);
	fa[y]=x;
}
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].dis);
	}
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=m;i++){
		int aa=get(a[i].x);
		int bb=get(a[i].y);
		if(aa==bb){
			cout<<a[i].dis<<endl;
			return 0;
		}
		if(!b[a[i].x]) b[a[i].x]=a[i].y;
		else hb(b[a[i].x],a[i].y);
		if(!b[a[i].y]) b[a[i].y]=a[i].x;
		else hb(b[a[i].y],a[i].x);
	}
	cout<<0<<endl;
	return 0;
}
2022/11/6 12:02
加载中...