简要题意：
给定若干组关系，第 \(i\) 组关系形如 “\(x\) 号罪犯和 \(y\) 号罪犯有 \(z\) 的矛盾”。现在共有两个*，在同一个*即会产生矛盾。问最小矛盾值。
显然，考虑 并查集 维护。
先按 \(z\) 从大到小排序，考虑一对对检验，不合法退出即可。
本题我们要维护 不等关系，即 \(x \not = y\) ，不能满足则答案为 \(z\).
不等关系如何维护？可以考虑一个 \(2\) 倍空间的方法.
显然，本题中，如果 \(a \not = b , b \not = c\)，则 \(a=c\)（\(a,b,c\) 为某罪犯关押的*编号且 \(\in (0,1)\)），所以 \(2\) 倍空间即可。（几个*就几倍）
考虑对于每组 \(x,y\)，本着 敌人的敌人是朋友 的原则，用\(f\) 表示 和自己一个*的集合，那么：
对于每组 \(x,y\)，用 \(f_x = f_y\) 或 \(f_{x+n} = f_{y+n}\) 表示 当且 \(x,y\) 在同一个*。可以理解一下：\(f_x = f_y\) 是显然，\(f_{x+n} = f_{y+n}\) 意为，两个人 同时和另一个人不在一个*，根据上面 \(a,b,c\) 的性质，可得两个人也是同一个*。
那么如何维护呢？显然，只要将 \(x\) 和 \(y+n\) 放在同一个*，\(y\) 和 \(x+n\) 放在同一个*，这样就解决了问题。
那么你问了：这样要枚举整个集合，怎么办？
我会平衡树！我会莫队！我会队列！我会 \(\text{set}\)！
不得不说，如果你给每个节点开 \(\text{set}\) 的话，显然 \(O(n^2)\) 空间等着你。
所以，可以发现 \(f_x\) 实际上记得是 和 \(x\) 同一个*的首领，而合并，查询等操作均为 并查集 维护操作。
综上可以通过。
时间复杂度：\(O(n \log n)\).（显然并查集常数 \(\alpha\) 不如排序多出的 \(\log n\) 大，忽略不计）
实际得分：\(100pts\).
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1;
inline int read(){char ch=getchar(); int f=1; while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}
int x=0; while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar(); return x*f;}
inline void write(int x) {
if(x<0) {putchar('-');write(-x);return;}
if(x<10) {putchar(char(x%10+'0'));return;}
write(x/10);putchar(char(x%10+'0'));
}
struct data {
int x,y,z;
} a[N];
int n,m,f[N];
inline bool cmp(data u,data v) {
return u.z>v.z;
} //排序
inline int find(int x) {return f[x]==x?x:f[x]=find(f[x]);} //查询
int main() {
n=read(),m=read();
for(int i=1;i<=m;i++) a[i].x=read(),a[i].y=read(),a[i].z=read();
sort(a+1,a+1+m,cmp);
int l=1,r=n,ans;
for(int i=1;i<=(n<<1);i++) f[i]=i;
for(int i=1;i<=m+1;i++) { //做到 m+1 是因为如果矛盾值为 0 则 i=m+1 时处理
int x=a[i].x,y=a[i].y,z=a[i].z;
if(find(x)==find(y) || find(x+n)==find(y+n)) {printf("%d\n",z);return 0;}
f[f[x+n]]=f[y]; f[f[x]]=f[y+n]; //合并
}
return 0;
}