P1525 [NOIP 2010 提高组] 关押罪犯
大意
给定若干对关系，让将这些人分入两个集合中，在同一集合中的两个有关系的人会贡献出来其边权，让求 \(\min(\max(s1, s2))\)。
思路
考虑二分图染色 + 二分。
很经典的话语：“最大值最小”，因此我们可以考虑二分答案，然后我们想想，二分完答案 \(k\) 之后怎么做？
显然对于哪些关系值小于等于 \(k\) 的我们是不是不需要考虑，只需要让关系值大于 \(k\) 的那些罪犯不在一个监狱中。
对于这个问题，差不多算 \(0 / 1\) 染色，只需要二分图染色，因为只有两个监狱，如果能染成功，就说明答案有可能小于等于 \(k\)，否则说明答案大于 \(k\)。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 20010;
struct node {int v, w;
};
vector<node> g[N];
int color[N], n, m;
bool dfs(int u, int k) {bool ok = true;for (int i = 0; i < g[u].size(); i++) {int v = g[u][i].v, w = g[u][i].w;if(w <= k) continue;if(color[v] == -1){color[v] = 1 - color[u];ok &= dfs(v, k);}else if(color[v] == color[u]){ok &= false;}}return ok;
}
bool check(int k) {memset(color, -1, sizeof(color));bool ok = true;for (int i = 1; i <= n; i++) {if (color[i] == -1) {color[i] = 0;ok &= dfs(i, k);}}return ok;
}
int main() {cin >> n >> m;for (int i = 0; i < m; i++) {int u, v, w;cin >> u >> v >> w;g[u].push_back({v, w});g[v].push_back({u, w});}int l = 0, r = 1000000001;while (l < r) {int mid = (l + r) >> 1;if (check(mid)) {r = mid;} else {l = mid + 1;}}cout << r;return 0;
}