洛谷题单指南-集合-P1525 [NOIP2010 提高组] 关押罪犯

原题链接：https://www.luogu.com.cn/problem/P1525

题意解读：有很多罪犯，要关到两座监狱，有一些罪犯之间有仇，并且可以量化出仇恨值，如果关在一起就会冲突，造成的影响就是仇恨值，要使得造成的影响最小，如果可以完全不起冲突，输出0。

解题思路：

首先，要让冲突影响最小化，显然应该把仇恨大的罪犯分开。

将所有罪犯关系、仇恨值按仇恨值大小降序排序

遍历每一对罪犯，判断他们是否已经在同一个集合（监狱）

如果已经属于同一个集合，则输出他们的仇恨值，即为答案。

如果不属于同一个集合，就要将两人分到两个集合（监狱），问题的关键来了，如何分配罪犯？

初始时，如果两人之前都没有仇人，则不着急合并，记录下两人为各自的仇人

接下来，如果两人能找到各自仇人，则将其与对方的仇人放在一个集合。（解释：a、b两人，a如果已经有仇人了，说明a和仇人的仇恨值更大，因为是在前面遍历到，a显然不能和其仇人分到一个集合，应该将b跟a的仇人分到一个集合，同样，a应该跟b的仇人分到一个集合）

100分代码：

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

const int N = 20005, M = 100005;

int p[N]; //并查集，罪犯所属的集合

//查找x所在集合
int find(int x)
{
    if(p[x] == x) return p[x];
    return p[x] = find(p[x]);
}
//将x、y合并
void merge(int x, int y)
{
    p[find(x)] = find(y);
}

struct node
{
    int a, b, c; //a 和 b的怨气值c
} s[M];

bool cmp(node x, node y)
{
    return x.c >= y.c;
}

int enemy[N]; //存储已出现的每个人的敌人-存在仇恨值的人
int n, m;

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        cin >> s[i].a >> s[i].b >> s[i].c;
    }

    for(int i = 1; i <= n; i++) p[i] = i;
    sort(s + 1, s + m + 1, cmp); //按仇恨值降序排序
    bool nowar = true; //是否没有任何冲突
    for(int i = 1; i <= m; i++)
    {
        int u = s[i].a, v = s[i].b;
        if(find(u) == find(v)) //如果两个人已经属于同一个集合，则无法再划分，此时的仇恨值即答案
        {
            cout << s[i].c;
            nowar = false; //说明会产生冲突
            break;
        }
        else
        {
            if(!enemy[u]) enemy[u] = v; //如果u没有敌人，给u设置敌人v
            else merge(enemy[u], v); //如果u有敌人，把v和u的敌人分到一个集合
            if(!enemy[v]) enemy[v] = u; //如果v没有敌人，给v设置敌人u
            else merge(enemy[v], u); //如果v有敌人，把u和v的敌人分到一个集合
        }
    }    
    if(nowar) cout << 0; //如果没有任何冲突，输出0

    return 0;
}