CH4901/洛谷1525 关押罪犯（贪心+并查集or二分+二分图染色）

我就是我 2021-11-13 23:18 258阅读 0赞

## 题意：有n个罪犯，其中有m对憎恨关系，表示a和b的怨气值为c。把这n个罪犯放到两个监狱中，使每个监狱里中最大的两罪犯的怒气值最小。输出这个最大的怒气值。 ##

## 分析：挺简单的一道题。 ##

## 方法一：贪心+并查集。**冲突值从大到小排序，先解决冲突值最大的纠纷，将两个罪犯放到不同的监狱，将放在同一个监狱的罪犯并到同一颗树（集合）上，再次遇到敌人时候可将这两个敌人并到一棵树上，若当前两个罪犯已经在同一颗树上，则该冲突值就是最大冲突值。** ##

## 方法二：二分+二分图染色。详见《算法竞赛进阶指南》P419。 ##

## 代码一（方法一）： ##

#include <iostream>
    #include <algorithm>
    using namespace std;
    const int N = 20006, M = 100006;
    int n, m, fa[N<<1];
    struct P {
    	int a, b, c;
    	bool operator < (const P x) const {
    		return c > x.c;
    	}
    } p[M];
    
    int get(int x) {
    	if (fa[x] == x) return x;
    	return fa[x] = get(fa[x]);
    }
    
    int main() {
    	cin >> n >> m;
    	for (int i = 1; i <= m; i++) cin >> p[i].a >> p[i].b >> p[i].c;
    	sort(p + 1, p + m + 1);
    	for (int i = 1; i <= (n << 1); i++) fa[i] = i;
    	for (int i = 1; i <= m; i++) {
    		int x = get(p[i].a), y = get(p[i].b);
    		int nx = get(p[i].a + n), ny = get(p[i].b + n);
    		if (x == y) {
    			cout << p[i].c << endl;
    			return 0;
    		}
    		fa[x] = ny;
    		fa[y] = nx;
    	}
    	cout << "0" << endl;
    	return 0;
    }

## 代码二（方法二）： ##

#include <cstdio>
    #include <vector>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    const int N = 20006, M = 200006;
    struct P {
    	int x, y, z;
    	bool operator < (const P w) const {
    		return z > w.z;
    	}
    } p[M];
    int n, m, v[N];
    vector<pair<int, int> > e[N];
    
    bool dfs(int x, int color) {
    	v[x] = color;
    	for (unsigned int i = 0; i < e[x].size(); i++) {
    		int y = e[x][i].first;
    		if (v[y]) {
    			if (v[y] == color) return 0;
    		} else {
    			if (!dfs(y, 3 - color)) return 0;
    		}
    	}
    	return 1;
    }
    
    inline bool pd(int now) {
    	for (int i = 1; i <= n; i++) e[i].clear();
    	for (int i = 1; i <= m; i++) {
    		if (p[i].z <= now) break;
    		e[p[i].x].push_back(make_pair(p[i].y, p[i].z));
    		e[p[i].y].push_back(make_pair(p[i].x, p[i].z));
    	}
    	memset(v, 0, sizeof(v));
    	for (int i = 1; i <= n; i++)
    		if (!v[i] && !dfs(i, 1)) return 0;
    	return 1;
    }
    
    int main() {
    	cin >> n >> m;
    	for (int i = 1; i <= m; i++)
    		scanf("%d %d %d", &p[i].x, &p[i].y, &p[i].z);
    	sort(p + 1, p + m + 1);
    	int l = 0, r = p[1].z;
    	while (l < r) {
    		int mid = (l + r) >> 1;
    		if (pd(mid)) r = mid;
    		else l = mid + 1;
    	}
    	cout << l << endl;
    	return 0;
    }