记录编号	585234	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010]关押罪犯	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.068 s
提交时间	2023-12-01 19:45:11	内存使用	2.81 MiB

#include <bits/stdc++.h> 
using namespace std;
#define ll long long
const int N = 4e4+10,M = 1e5+10;
int n,m,ans;
int fa[N];
int find(int x){
	if(x == fa[x])return x;
	return fa[x] = find(fa[x]);
}
void merge(int x,int y){
	x = find(x),y = find(y);
	if(x == y)return;
	fa[x] = y;
}
struct made{
	int x,y,z;
	bool operator < (const made u)const{
		return z > u.z;
	}
}a[M];
int main(){
	freopen("prison1.in","r",stdin);
	freopen("prison1.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= m;i++)scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
    sort(a+1,a+1+m);
    for(int i = 1;i <= 2*n;i++)fa[i] = i;
    for(int i = 1;i <= m+1;i++){
    	if(find(a[i].x) == find(a[i].y)){
    		printf("%d\n",a[i].z);
    		break;
		}
		merge(a[i].x,a[i].y+n);
		merge(a[i].x+n,a[i].y);
	}
	
	return 0;
	
}