P1525 [NOIP2010 提高组] 关押罪犯
法一：二分图
把犯人分配到两个监狱，使得监狱内的怒气值最大最小
分配到两个集合中，考虑二分染色
分析因为答案具有单调性所以可以二分：
判断x是否符合，只需要重建大于x的边，如果不能把它们分到两个集合中（二分染色失败），就往上调（考虑无限大，那么就不矛盾）
当然也可无需重建，只需要跳过即可
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, m;
struct node {
int u, v, s;
}a[N];
int cnt,h[N], ne[2 * N], to[2 * N], w[2 * N];
void add(int a, int b, int c) {
ne[++cnt] = h[a];
to[cnt] = b;
w[cnt] = c;
h[a] = cnt;
}
int color[N];
bool dfs(int x,int c,int k) {
color[x] = c;
for (int i = h[x]; i; i = ne[i]) {
if (w[i] < k) continue;//跳过
if (!color[to[i]]) {
if (dfs(to[i], 3 - c, k)) return 1;
}
else if (color[to[i]] == c) return 1;
}
return 0;
}
bool check(int x) {//模板
for (int i = 1; i <= n; i++) {
if (!color[i]) {
if (dfs(i,1,x)) return false;
}
}
return true;
}
int main() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
add(b, a, c);
}
int l = 0, r = 1e9 + 10;
while (l + 1 < r) {
memset(color, 0, sizeof color);//清零
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid;
}
cout << l;
return 0;
}
法二：种类并查集
如果你出错可能是因为排序的长度写成了n（不要问我怎么知道的）
1.要想怒气值小，必定是要把怒气值大的两人分开，因此要从大到小排序（事无绝对）
2.把两人分开，注意：敌人的敌人是朋友，因为它没地方可去
3.如果两人在同一集合，那么直输出：如果把两人分开，必定会造成更大的怒气值，因为排过序
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, m;
struct node {
int u, v, s;
}a[N];
int f[N * 2];
int find(int x) {
return f[x] == x ? x : f[x] = find(f[x]);
}
void unit(int x, int y) {
int fx = find(x), fy = find(y);
f[fx] = fy;
}
int main() {
cin >> n >> m;
for (int i = 1; i <= 2 * n; i++) f[i] = i;
for (int i = 1; i <= m; i++) {
cin >> a[i].u >> a[i].v >> a[i].s;
}
sort(a + 1, a + 1 + m, [](node x, node y) {//排序为m
return x.s > y.s;
});
for (int i = 1; i <= m; i++) {
int x=a[i].v, y = a[i].u;
if (find(x)==find(y)) {
cout << a[i].s;
break;
}
else {
unit(x, y + n);
unit(y,x + n);
}
if (i == m) cout << 0;
}
return 0;
}