NOIP2010提高组.关押罪犯

题目

257. 关押罪犯

算法标签: 二分图染色, 二分

思路

首先观察到答案具有二分性, 假设最优解是$mid$, 小于$mid$的无法构成二分图, 但是大于等于$mid$的是可以构成二分图的, 每次判断的时候判断, 所有仇恨关系大于$mid$的边, 然后将这两个罪犯放到两个监狱当中

$dfs$染色代码, 如果没有剪枝优化容易爆栈

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

const int N = 20010, M = 200010;


int n, m;
int head[N], ed[M], ne[M], w[M], idx;
int col[N];

void add(int u, int v, int val) {
   
	ed[idx] = v, ne[idx] = head[u], w[idx] = val, head[u] = idx++;
}

bool dfs(int u, int fa, int val, int mid) {
   
	col[u] = val;
	for (int i = head[u]; ~i; i = ne[i]) {
   
		int v = ed[i];
		if (v == fa) continue;
		if (w[i] <= mid) continue;
		if (col[v] == -1) {
   
			if (!dfs(v, u, 3 - val, mid)) return false;
		}
		else if (col[v] == val) return false;
	}
	return true;
}

bool check(int mid) {
   
	memset(col, -1, sizeof col);
	for (int i = 1; i <= n; ++i) {
   
		if (col[i] != -1) continue;
		if (!dfs(i, -1, 1, mid)) return false;
	}
	return true;
}

int main() {
   
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	memset(head, -1, sizeof head);
	cin >> n >> m;

	while (m--) {
   
		int u, v, w;
		cin >> u >> v >> w;
		add(u, v, w);
		add(v, u, w);
	}

	int l = 0, r = 1e9;
	while (l < r) {
   
		int mid = l + r >> 1;
		if (check(mid)) r = mid;
		else l = mid + 1;
	}

	cout << l << "\n";

	return 0;
}

$bfs$写法

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;

const int N = 20010, M = 100010;

int n, m;
int head[N], ed[M], ne[M], w[M], idx;
int col[N];

void add(int u, int v, int val) {
   
	ed[idx] = v, ne[idx] = head[u], w[idx] = val, head[u] = idx++;
}

bool bfs(int u, int mid) {
   
	queue<int> q;
	q.push(u);
	col[u] = 1;

	while (!q.empty()) {
   
		int u = q.front();
		q.pop();

		for (int i = head[u]; ~i; i = ne[i]) {
   
			int v = ed[i];
			if (w[i] <= mid) continue;

			if (col[v] == -1) {
   
				col[v] = 3 - col[u];
				q.push(v);
			}
			else if (col[v] == col[u]) {
   
				return false;
			}
		}
	}
	return true;
}

bool check(int mid) {
   
	memset(col, -1, sizeof col);
	for (int i = 1; i <= n; ++i) {
   
		if (col[i] == -1) {
   
			if (!bfs(i, mid)) return false;
		}
	}
	return true;
}

int main() {
   
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	memset(head, -1, sizeof head);
	cin >> n >> m;

	while (m--) {
   
		int u, v, w;
		cin >> u >> v >> w;
		add(u, v, w);
		add(v, u, w);
	}

	int l = 0, r = 1e9;
	while (l < r) {
   
		int mid = l + r >> 1;
		if (check(mid)) r = mid;
		else l = mid + 1;
	}

	cout << l << "\n";

	return 0;
}