题目链接：https://ac.nowcoder.com/acm/contest/258/C
题目大意：
略
分析：
这题是并查集的一个变题，先按积怨值从大到小排序，然后一个一个看能否完全分开，遇到的第一个不能分开的囚犯对（如果强行分开就必然有更高的积怨值出现）就是答案。
一开始想到的是按监狱数量弄个并查集，后来发现并不行，因为如果要分开一对囚犯，没办法决定谁一定住1号监狱，谁一定住2号监狱。后来试了下用囚犯数量弄并查集，发现也不行，因为没有积怨的才能放一个集合里，比如1和2有积怨不在一起，3和4有积怨不在一起，那1和3,1和4等等就没法确定，那把他们都放不同集合里？不行，因为不在一个集合的可能有积怨可能没积怨。
让后我就想当选取到i + 1对囚犯时，前i对囚犯必然也形成一张图，这张图可能不是连通的，换句话说，就是包含多个极大联通子图（囚犯小团体），小团体与小团体之间互相没有积怨，因为程序已经选取到了i + 1对囚犯，所以这些小团体内部必然可以两两分开以致于没有积怨。选取其中一个小团体，如果这个极大联通子图没有坏，那必然可以变形成如下形式：
也就是说，肯定可以一刀切。
如果有环，那促成环的这条线的两端必分别属于左右两边：
如果这个时候来了一条边，它的两个端点都在这张图的一边：
那这张图必然怎么切都切不开了。
也就是说，如果第i + 1对囚犯都属于某一个小团体的一边，答案就出来了。
也就是说每名囚犯应该有2个状态i和i'，上面的图应该是这样：
于是并查集的长度应该为2n，前n个表示1~n，后n个表示1'~n'。
PS：代码中并没有判断是否在都一边而是直接判断在不在一个集合，这是因为是直接查找的同一边的点，就是没有'的那边，这样直接判断在不在一个集合就可以了。
代码如下：
#include <bits/stdc++.h>
using namespace std; #define rep(i,n) for (int i = 0; i < (n); ++i)
#define For(i,s,t) for (int i = (s); i <= (t); ++i)
#define rFor(i,t,s) for (int i = (t); i >= (s); --i)
#define foreach(i,c) for (__typeof(c.begin()) i = c.begin(); i != c.end(); ++i)
#define rforeach(i,c) for (__typeof(c.rbegin()) i = c.rbegin(); i != c.rend(); ++i) #define pr(x) cout << #x << " = " << x << " "
#define prln(x) cout << #x << " = " << x << endl #define ALL(x) x.begin(),x.end()
#define INS(x) inserter(x,x.begin()) #define ms0(a) memset(a,0,sizeof(a))
#define msI(a) memset(a,inf,sizeof(a)) #define pii pair<int,int>
#define piii pair<pair<int,int>,int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second inline int gc(){
static const int BUF = 1e7;
static char buf[BUF], *bg = buf + BUF, *ed = bg; if(bg == ed) fread(bg = buf, , BUF, stdin);
return *bg++;
} inline int ri(){
int x = , f = , c = gc();
for(; c<||c>; f = c=='-'?-:f, c=gc());
for(; c>&&c<; x = x* + c - , c=gc());
return x*f;
} typedef long long LL;
const int maxN = 1e5 + ; struct Edge{
int X, Y, W; Edge() {}
Edge(int x, int y, int w) : X(x), Y(y), W(w) {} bool operator < (const Edge &x) const {
return W > x.W;
}
}; int n, m, ans;
Edge e[maxN];
int f[maxN]; int Find(int x){
while (x != f[x]) x = f[x] = f[f[x]];
return x;
} int main(){
n = ri();
m = ri(); For(i, , m) {
e[i].X = ri();
e[i].Y = ri();
e[i].W = ri();
}
sort(e+, e+m+);
For(i, , n<<) f[i] = i; For(i, , m) {
int x = e[i].X, y = e[i].Y;
x = Find(x);
y = Find(y);
if(x == y) {
ans = e[i].W;
break;
}
f[x] = Find(e[i].Y + n);
f[y] = Find(e[i].X + n);
} printf("%d\n", ans);
return ;
}