P1525 [NOIP2010 提高组] 关押罪犯 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

种类并查集

#include <bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<'\n';

using namespace std;
using i64 = long long;

typedef pair<i64, i64> PII;

struct UFS {
	int sz;
	vector<int> rank, p;
	void link(int x, int y) {
		if (x == y)
			return;
		if (rank[x] > rank[y])
			p[y] = x;
		else
			p[x] = y;
		if (rank[x] == rank[y])
			rank[y]++;
	}
	void init(int n) {
		sz = n;
		rank.resize(n + 1);
		p.resize(n + 1);
		for (int i = 0; i <= sz; i++) {
			p[i] = i;
			rank[i] = 0;
		}
	}
	int find(int x) {
		return x == p[x] ? x : (p[x] = find(p[x]));
	}
	void unin(int x, int y) {
		link(find(x), find(y));
	}
	void compress() {
		for (int i = 0; i <= sz; i++)
			find(i);
	}
};
//种类并查集 merge(y + n, x),merge(x + n, y)

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, m;
	cin >> n >> m;
	vector<pair<i64, PII>> g;
	for (int i = 0; i < m; i ++) {
		i64 u, v, w;
		cin >> u >> v >> w;
		g.emplace_back(w, PII(u, v));
	}

	sort(g.begin(), g.end(), greater<>());
	UFS ufs;
	ufs.init(2 * n);
	i64 ans = 0;
	for (int i = 0; i < m; i ++) {
		auto [w, uv] = g[i];
		auto [u, v] = uv;
		if (ufs.find(u) == ufs.find(v) || ufs.find(u + n) == ufs.find(v + n)) {
			ans = w;
			break;
		}
		ufs.unin(u + n, v);
		ufs.unin(v + n, u);
	}

	cout << ans << '\n';

	return 0;
}

二分+二分图染色

二分最大的影响力,大于\(mid\)的罪犯就必须分开,然后看判定所有的罪犯是否可以分成两个集合

#include <bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<'\n';

using namespace std;
using i64 = long long;

typedef pair<i64, i64> PII;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, m;
	cin >> n >> m;
	vector g(n + 1, vector<PII>());
	for (int i = 0; i < m; i ++) {
		i64 u, v, w;
		cin >> u >> v >> w;
		g[u].emplace_back(v, w);
		g[v].emplace_back(u, w);
	}

	auto check = [&](i64 mid) {
		vector<int> col(n + 1, -1);
		queue<int> Q;
		for (int i = 1; i <= n; i ++) {
			if (col[i] == -1) {
				Q.push(i);
				col[i] = 0;
				while (Q.size()) {
					auto u = Q.front();
					Q.pop();
					for (auto [v, w] : g[u]) {
						if (w > mid) {
							if (col[v] == -1) {
								col[v] = col[u] ^ 1;
								Q.push(v);
							} else if (col[v] == col[u])
								return false;
						}
					}
				}
			}
		}
		return true;
	};


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

	cout << ans << '\n';

	return 0;
}