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;
}