本文共 2701 字，大约阅读时间需要 9 分钟。

题目描述

$S$ 城现有两座监狱，一共关押着 $N$ 名罪犯，编号分别为 $1-N$ 。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久，如果客观条件具备则随时可能爆发冲突。

我们用“怨气值”（一个正整数值）来表示某两名罪犯之间的仇恨程度，怨气值越大，则这两名罪犯之间的积怨越多。如果两名怨气值为 $c$ 的罪犯被关押在同一监狱，他们俩之间会发生摩擦，并造成影响力为 $c$ 的冲突事件。

每年年末，警察局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表，然后上报到 $S$ 城 $Z$ 市长那里。公务繁忙的 $Z$ 市长只会去看列表中的第一个事件的影响力，如果影响很坏，他就会考虑撤换警察局长。

在详细考察了 $N$ 名罪犯间的矛盾关系后，警察局长觉得压力巨大。他准备将罪犯们在两座监狱内重新分配，以求产生的冲突事件影响力都较小，从而保住自己的乌纱帽。

假设只要处于同一监狱内的某两个罪犯间有仇恨，那么他们一定会在每年的某个时候发生摩擦。那么，应如何分配罪犯，才能使 $Z$ 市长看到的那个冲突事件的影响力最小？这个最小值是多少？

输入格式

每行中两个数之间用一个空格隔开。第一行为两个正整数 $N,M$ ，分别表示罪犯的数目以及存在仇恨的罪犯对数。接下来的 $M$ 行每行为三个正整数 $a_j,b_j,c_j$ ，表示 $a_j$ 号和 $b_j$ 号罪犯之间存在仇恨，其怨气值为 $c_j$ 。数据保证 $1<a_j\le b_j\le N,0<c_j\le 10^9$，且每对罪犯组合只出现一次。

输出格式

共 $1$ 行，为 $Z$ 市长看到的那个冲突事件的影响力。如果本年内监狱中未发生任何冲突事件，请输出 $0$ 。

输入输出样例

输入 #1

4 61 4 25342 3 35121 2 283511 3 66182 4 18053 4 12884

输出 #1

3512

说明/提示

【输入输出样例说明】罪犯之间的怨气值如下面左图所示，右图所示为罪犯的分配方法，市长看到的冲突事件影响力是 $3512$（由 $2$ 号和 $3$ 号罪犯引发）。其他任何分法都不会比这个分法更优。

【数据范围】

• 对于 $30\%$ 的数据有 $N\le 15$ 。
• 对于 $70\%$ 的数据有 $N\le 2000,M\le 50000$ 。
• 对于 $100\%$ 的数据有 $N\le 20000,M\le 100000$ 。

题意：合理分配囚犯的监狱位置，使得可能爆发出的冲突事件的影响尽可能小。

---

思路：贪心，我们把冲突按照影响力从大到小排序，然后尽可能地关到不同的监狱中，直到不能够将两个囚犯分到不同的监狱中为止——或者说，以前分配的时候间接将他们两个分到了同一个监狱之中。如果都能够合理分配，没有冲突时一定要输出 $0$ 。

具体做法是：开一个 $n\ast 2$ 的并查集，分为区间 $1\sim n$ 与区间 $n+1\sim 2n$ ，合并在相同集合表示在同一监狱，不同集合表示之间是敌人。 我们把输入数据按怨气值从大到小排序，然后尽量把怨气值高的犯人分到两个监狱中。若发现有两个罪犯 $x,y$ ，在之前已被划分为同一监狱，又在接下来的数据处理中发现他俩有矛盾，则冲突不可避免 ，直接输出。如果所有矛盾都可避免，则输出 $0$ 。

代码如下：

#include 
   
    using namespace std;struct node {
   	int a, b, w;} c[100010];int father[40010], height[40010]; //种类并查集和高度数组void init(int n) {
   	for (int i = 1; i <= n; ++i) height[i] = 1, father[i] = i;}int find(int x) {
   	return father[x] == x ? x : father[x] = find(father[x]);}void merge(int a, int b) {
    	int x = find(a), y = find(b);	if (x == y) return;	//合并两个不同的集合 	if (height[x] >= height[y]) father[y] = x;	else father[x] = y;	if (height[x] == height[y]) ++height[x];}int main() {
   	int n, m;	scanf("%d%d", &n, &m);	init(n * 2); 	//罪犯i,其敌人是i+n,即不处于同一个监狱内	for (int i = 0; i < m; ++i) 		scanf("%d%d%d", &c[i].a, &c[i].b, &c[i].w);	sort(c, c + m, [&](const node &a, const node &b) {
   		return a.w > b.w; 	});	for (int i = 0; i < m; ++i) {
   		int r1 = find(c[i].a), r2 = find(c[i].b);		if (r1 == r2) {
    //两个罪犯已经处于同一个监狱			printf("%d\n", c[i].w);			break;		} 		merge(c[i].a, c[i].b + n);		merge(c[i].b, c[i].a + n);		if (i == m - 1) puts("0"); //如果循环结束时仍然没有冲突,输出0	}    return 0;}
   

提交后AC：

转载地址：https://memcpy0.blog.csdn.net/article/details/108287679 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！