P1525 [NOIP2010 提高组] 关押罪犯 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

 因为要求所有冲突值最大的要最小，而且答案具有单调性，最大数值大了容易分配，小了不容易分配。容易想到二分枚举答案。然后就是如何判断这个答案是否合法。当前答案为mid，那么比mid大的冲突就不能发生，又因为有两个监狱，每个人必定在其中一个，那么比当前枚举的答案大的边（两个人的冲突值）构成一个二分图，也就是说有冲突（边）的两个犯人在相对的监狱，并且同一个监狱没有冲突则符合要求。所以想到用二分图染色判断比mid大的边构成的图是否构成二分，如果是则这个答案合法。

#include
using namespace std;
#pragma warning(disable:4996);
#define int long long 
#define rep(j,b,e) for(int j=(b);j<=(e);j++)
#define drep(j,e,b) for(int j=(e);j>=(b);j--)
const int N = 2e5 + 10;
int T = 1;
int n, m, k;
struct node {
	int t, v;
};
struct edge {
	int f, t, v;
}edg[N];
vectorgra[N];
int vis[N];
int match[N];
int val[N];
int fnd(int now, int tar) {//二分图匹配
	for (auto [nx, v] : gra[now]) {
		if (vis[nx] == 0) {
			vis[nx] = 1;
			if ((match[nx] == 0 && v <= tar) || fnd(match[nx], tar)) {
				match[nx] = now;
				return 1;
			}
		}
	}
	return 0;
}
int color[N];
int dfs(int tar, int now, int c) {//二分图染色
	color[now] = c;
	for (auto& [nx, v] : gra[now]) {
		if (v < tar)continue;
		if (color[nx] == 0) {
			if (dfs(tar, nx, 3 - c) == 0)
				return 0;
		}
		else if (color[nx] == c)
			return 0;
	}
	return 1;
}
int check(int tar) {//二分判断函数
	int ok = 1;
	rep(j, 1, n) {
		if (color[j])continue;
		if (dfs(tar, j, 1) == 0)
			ok = 0;
	}
	return ok;
}
int mx = INT_MIN;
int bi_find() {//二分查找
	int l = 0, r = mx + 1;
	int mid;
 
	while (l + 1 != r) {
		mid = (l + r) >> 1;
		memset(color, 0, sizeof(color));
		if (check(mid))
			r = mid;
		else
			l = mid;
	}
	return l;
}
 
signed main() {
#ifndef ONLINE_JUDGE
	//freopen("out.txt", "w", stdout);
	freopen("in.txt", "r", stdin);
#endif
	ios::sync_with_stdio(0); cout.tie(0);
	cin >> n >> m;
	rep(j, 1, m) {
		int f, t, v;
		cin >> f >> t >> v;
		mx = max(mx, v);
		gra[f].push_back({ t,v });
		gra[t].push_back({ f,v });
		edg[j] = { f,t,v };
	}
	cout << bi_find();
}