Significance: There are n criminals, among whom m has hatred relationship, indicating that the resentment value of a and b is c. Put n criminals in two prisons to minimize the anger of the two largest criminals in each prison. Output this maximum rage value.

Analysis: A very simple question.

Method 1: Greed + Collect. The conflict value is sorted from large to small. First, the disputes with the largest conflict value are solved. Two criminals are put in different prisons, and the criminals in the same prison are merged into the same tree (collection). When they encounter the enemy again, they can be merged into a tree. If the two criminals are already on the same tree, the conflict value is the maximum conflict value.

Method 2: Bipartite + Bipartite graph staining. See "Advanced Guide to Algorithmic Competition" P419 for details.

Code 1 (Method 1):

#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;
}

Code 2 (Method 2):

#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;
}