P1525 NOIP2010 提高组 关押罪犯 题解

Link: P1525 NOIP2010 提高组 关押罪犯 - 洛谷

分析

首先题目给出了罪犯与罪犯之间的矛盾关系，这让我们可以想到图或并查集。然后，题目又说了要把罪犯分入两个监狱，也就是把罪犯看作点，要把这些点分入两个集合，这很自然地可以想到二分图。再然后，市长只会去看列表中的第一个事件的影响力，而我们希望这个影响力最大的事件影响最小，所以又可以想到用二分来寻找答案。

到这个地步，做这道题的要素已经集齐，我们继续分析具体怎么做。首先我们通过二分来枚举最大影响力，然后考虑如何判断是否合法。既然我们希望会造成大影响的罪犯尽量被分在两个监狱里，那么我们可以在通过染色判定二分图的时候加一个条件，即只有边权大于等于当前枚举的最大影响力时，我们才考虑将两个罪犯放在不同监狱里面（学过二分图应该看得懂这句话）。在这个限制下，如果染色完二分图合法，那么我们就接着尝试检测更小的答案；否则，说明当前答案过小，导致影响力大于等于当前答案的所有罪犯不能被正确地分入两个监狱，接下来要尝试更大检测更大的答案。

注意二分答案的写法，比较奇特 反正我没见过，是我练得还太少了。

代码

#include <bits/stdc++.h>
using namespace std;

const int maxn = 20005;
const int maxm = 100005;
int n, m;
int head[maxn];
struct Edge {
	int to, next, weight;
} edge[maxm << 1];

inline void insertEdge(int u, int v, int w) {
	static int edgecnt;
	edge[++edgecnt].to = v;
	edge[edgecnt].weight = w;
	edge[edgecnt].next = head[u];
	head[u] = edgecnt;
}

int color[maxn];
bool dfs(int u, int col, int anger) {
	color[u] = col;
	for (int i = head[u]; i; i = edge[i].next) {
		int v = edge[i].to, w = edge[i].weight;
		if (w < anger) continue;
		if (!color[v]) {
			if (!dfs(v, 3 - col, anger)) return false;
		} else if (color[u] == color[v]) return false;
	}
	return true;
}

inline bool check(int anger) {
	memset(color, 0, sizeof(color));
	for (int i = 1; i <= n; i++) {
		if (!color[i]) {
			if (!dfs(i, 1, anger)) return false;
		}
	}
	return true;
}

int main() {
	scanf("%d%d", &n, &m);
	int l = 0, r = 0;
	for (int i = 1; i <= m; i++) {
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		insertEdge(u, v, w);
		insertEdge(v, u, w);
		r = max(r, w);
	}
	while (l + 1 < r) {
		int mid = (l + r) >> 1;
		if (check(mid)) r = mid;
		else l = mid;
	}
	printf("%d", l);
	return 0;
}