错误半天还是因为并查集写错了。写错的地方是合并X和Y的时候，应该把FX挂到FY上去，而不是把X挂到Y上或FY上去，因为FX和FY下面有一树别的节点。 http://www.nocow.cn/index.php/%E5%B9%B6%E6%9F%A5%E9%9B%86
加强印象，仔细看图：
本题的思路有两种，一是求最大值最小，而已二分+BFS来做，但效率较低。更好的做法是贪心+并查集。先按照怨念排序，然后从大到小判断是否有冲突。
判断冲突的时候用了个巧妙的方法，就是A和B不能放在一组，那么设A的补集为!A，B的补集!B，那么merge(A, !B) 且merge(B, !A)，这样当有A不能和B在一起，C不能和B在一起时，由于A和C都在!B一组里了，merge时会冲突。i的补集用i+n来表示，所以开2N的数组。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <memory.h>
#define MAX(a, b) a>b?a:b
#define LEN_N 20005
#define LEN_M 100005
using namespace std; struct Conflict
{
int a;
int b;
int val;
}; int N;
int M;
int father[LEN_N*2];
Conflict edges[LEN_M]; bool comp(Conflict a, Conflict b)
{
return a.val > b.val;
} int find(int i) {
if (father[i] != i) {
father[i] = find(father[i]);
}
return father[i];
} void merge(int i, int j) {
father[find(i)] = find(j);
} void init()
{
memset(edges, 0, sizeof(edges));
memset(father, 0, sizeof(father));
scanf("%d%d", &N, &M);
for (int i = 0; i < M; i++) {
scanf("%d%d%d", &edges[i].a, &edges[i].b, &edges[i].val);
}
for (int i =1; i <= N*2; i++) {
father[i] = i;
}
} int main()
{
init();
sort(edges, edges+M, comp);
int ans = 0;
for (int i = 0; i < M; i++) {
int a = edges[i].a;
int b = edges[i].b;
if (find(a) == find(b)) {
// conflict
ans = edges[i].val;
break;
}
merge(a, b+N);
merge(b, a+N);
} printf("%d\n", ans);
return 0;
}