本文主要是介绍NOIP2010 关押罪犯 (二分答案+二分图染色)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：有两个监狱，N个犯人，M对关系，每对关系描述一对犯人如果在一个监狱将会产生一个冲突值。任意安排犯人的分配，使得产生的最大冲突值最小。
题解：最大值最小，先考虑二分。二分中最重要的环节就是判定猜测值可行性以及保证答案单调性。可行性判定：对于一个猜测的最大冲突值，判定时就要保证所有大于这个冲突值的两个人不能在一个监狱。只需要将需要满足不在同一监狱的两个人连上边，如果最后可以染成二分图，就存在分配方案，当然，有可能图不连通，只需要每个连通块可以染成二分图即可。单调性：猜测的值越大，会连的边就越少，单个连通块就越小，每个连通块染色成功的几率就越大。
二分的时候要注意细节，最好是将边权排序后在边权数组上进行二分（当然还要引入0），这样保证答案在原数组中出现。如果是在负无穷到正无穷之间二分，要注意尽量取最大的可行解才能保证在原数组出现，并且下界应该注意好并且保证你的写法在答案=0时也可以出正解。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 20010, MAXM = 200010;
struct Node {int to; Node*next;
}Edge[MAXM], *ecnt=Edge, *adj[MAXM];
void addedge(int a, int b) {++ecnt; ecnt->to = b;ecnt->next=adj[a]; adj[a] = ecnt;
}
int N, M, mx;
int x[MAXM], y[MAXM], z[MAXM];void BuildGraph(int lim)
{ecnt = Edge;memset(adj, 0, sizeof adj);for (int i = 1; i<=M; ++i)if (z[i] > lim) {addedge(x[i], y[i]);addedge(y[i], x[i]);}
}int color[MAXN];
bool flag; //flag=1代表染色失败
void dfs(int u)
{if (!flag) return;for (Node*p = adj[u]; p; p=p->next){int &v = p->to;if (color[v] == -1) {color[v] = color[u]^1;dfs(v);}else if (color[v] == color[u]) {flag=0; return; }}
}int work()
{int l = -1, r = mx, mid;while (l+1 < r) {mid = (l + r) >> 1;BuildGraph(mid);memset(color, -1, sizeof color);flag = 1;for (int i = 1; i<=N; ++i) {if (color[i]==-1) { color[i] = 0; dfs(i); }if (!flag) break; } if (flag) r = mid;else l = mid; } return r;
}int main()
{scanf("%d%d", &N, &M);for (int i = 1; i<=M; ++i) {scanf("%d%d%d", &x[i], &y[i], &z[i]);if (z[i] > mx) mx = z[i];}printf("%d\n", work());return 0;
}
这篇关于NOIP2010 关押罪犯 (二分答案+二分图染色)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
