4 6

1 4 2534

2 3 3512

1 2 28351

1 3 6618

2 4 1805

3 4 12884

3512

【数据范围】对于30%的数据有N≤ 15。对于70%的数据有N≤ 2000，M≤ 50000。对于100%的数据有N≤ 20000，M≤ 100000。

# 幷查集

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#define ri register int
#define MAXN 500000
using namespace std;
inline void re(int &x)
{
x = 0;
char ch = getchar();
int b = 0;
while(ch < '0' || ch > '9'){
if(ch == '-') b = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9'){
x = (x << 1) + (x << 3) + ch - '0';
ch = getchar();
}
if(b == -1)
x *= -1;
}
struct edge
{
int f,to,c;
}qwq[MAXN];
int n,m,ans;
int fa[MAXN];
inline bool cmp(edge x,edge y)
{
return x.c > y.c;
}
int find(int x)
{
if(fa[x] != x) fa[x] = find(fa[x]);
return fa[x];
}
inline void merge(int x,int y)
{
int da = find(x);
int mm = find(y);
if(da != mm) fa[da] = mm;
}
int main()
{
re(n),re(m);
for(ri i = 1;i <= m;i ++){
re(qwq[i].f),re(qwq[i].to),re(qwq[i].c);
}
for(ri i = 1;i <= 2*n;i ++)
fa[i] = i;
sort(qwq + 1,qwq + 1 + m,cmp);
for(ri i = 1;i <= m;i ++){
int l = qwq[i].f;
int r = qwq[i].to;
if(find(l) != find(r)){
merge(l,r + n);
merge(r,l + n);
}
else{
printf("%d",qwq[i].c);
return 0;
}
}
printf("%d",0);
return 0;
}