题意：有n个罪犯，其中有m对憎恨关系，表示a和b的怨气值为c。把这n个罪犯放到两个监狱中，使每个监狱里中最大的两罪犯的怒气值最小。输出这个最大的怒气值。
分析：挺简单的一道题。
方法一：贪心+并查集。冲突值从大到小排序，先解决冲突值最大的纠纷，将两个罪犯放到不同的监狱，将放在同一个监狱的罪犯并到同一颗树（集合）上，再次遇到敌人时候可将这两个敌人并到一棵树上，若当前两个罪犯已经在同一颗树上，则该冲突值就是最大冲突值。
方法二：二分+二分图染色。详见《算法竞赛进阶指南》P419。
代码一（方法一）：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 20006, M = 100006;
int n, m, fa[N<<1];
struct P {int a, b, c;bool operator < (const P x) const {return c > x.c;}
} p[M];int get(int x) {if (fa[x] == x) return x;return fa[x] = get(fa[x]);
}int main() {cin >> n >> m;for (int i = 1; i <= m; i++) cin >> p[i].a >> p[i].b >> p[i].c;sort(p + 1, p + m + 1);for (int i = 1; i <= (n << 1); i++) fa[i] = i;for (int i = 1; i <= m; i++) {int x = get(p[i].a), y = get(p[i].b);int nx = get(p[i].a + n), ny = get(p[i].b + n);if (x == y) {cout << p[i].c << endl;return 0;}fa[x] = ny;fa[y] = nx;}cout << "0" << endl;return 0;
}
代码二（方法二）：
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 20006, M = 200006;
struct P {int x, y, z;bool operator < (const P w) const {return z > w.z;}
} p[M];
int n, m, v[N];
vector<pair<int, int> > e[N];bool dfs(int x, int color) {v[x] = color;for (unsigned int i = 0; i < e[x].size(); i++) {int y = e[x][i].first;if (v[y]) {if (v[y] == color) return 0;} else {if (!dfs(y, 3 - color)) return 0;}}return 1;
}inline bool pd(int now) {for (int i = 1; i <= n; i++) e[i].clear();for (int i = 1; i <= m; i++) {if (p[i].z <= now) break;e[p[i].x].push_back(make_pair(p[i].y, p[i].z));e[p[i].y].push_back(make_pair(p[i].x, p[i].z));}memset(v, 0, sizeof(v));for (int i = 1; i <= n; i++)if (!v[i] && !dfs(i, 1)) return 0;return 1;
}int main() {cin >> n >> m;for (int i = 1; i <= m; i++)scanf("%d %d %d", &p[i].x, &p[i].y, &p[i].z);sort(p + 1, p + m + 1);int l = 0, r = p[1].z;while (l < r) {int mid = (l + r) >> 1;if (pd(mid)) r = mid;else l = mid + 1;}cout << l << endl;return 0;
}
