洛谷 P1525 【关押罪犯】种类并查集

时间:2022-08-28 14:36:20

题解 P1525 【关押罪犯】:种类并查集

前言:

在数据结构并查集中,种类并查集属于扩展域并查集一类。

比较典型的题目就是:食物链(比本题难一些,有三个种类存在)

首先讲一下本题的贪心,这个是必须要懂的。我们假设最后Z 市长看到的那个冲突事件的影响力为 x (也就是有一对仇恨值为 x 的罪犯在同一*)那么比 x 仇恨值更高的每一对罪犯必须分配到不同的*(不然,最终答案就不是 x ,而是这一对罪犯的仇恨值了);

所以本题是存在单调性的,只需要从大到小枚举仇恨值,到那一对与前面出现矛盾了,直接输出即可;

思路:

种类并查集中“种类”这个词也不是绝对的,它也可以说是一种关系,而本题的关系就在于要将罪犯分配到的两个*;我们可以将数组开到两倍来模拟这两个*(用A,B表示),每个罪犯在*中都有一个位置。

假设现在要把两个有仇的罪犯分别放到 A 或 B 中,我们发现如果要满足这一对的要求(即分到的*不同),那么如果第一个罪犯在 A *,第二个罪犯必须在 B *,反之也一样。

所以我们可以将 A *中第一个罪犯的位置与 B *中第二个罪犯的位置用并查集维护,即这样合并才能保证分到的*不一样。但第一个罪犯不一定只能在 A *,所以我们将 B *中 第一个罪犯的位置与 A *中第二个罪犯的位置维护。

而出现矛盾的情况,举个例子: a 和 c 有仇,b 和 c 有仇,那么此时 a 和 c 在不同*,b 和 c 也在不同*,也就是说 a 和 b 一定在一个*。可一旦此时 a 和 b 有仇那么就矛盾了,因为a 和 b 要在不同*不然会有矛盾,可 a 和 b 已经在之前判定为必须在同一*,所会矛盾,此时就可以直接输出 a 和 b 的仇恨值(原理参见前言的贪心)

代码实现:

#include<iostream>
#include<cstdio>
#include<iomanip>
#include<algorithm>
#define rg register int//卡常

using namespace std;

struct su{
    int f,t,v;
}a[100010];

int n,m,l,r,mid,f;
int s[20001<<1]; //不要单独开两数组!

inline int qr(){  char ch; //快读
    while((ch=getchar())<'0'||ch>'9');
    int res=ch^48;
    while((ch=getchar())>='0'&&ch<='9')
        res=res*10+(ch^48);
    return res;
}

inline bool cmp(su x,su y){
    return x.v>y.v; //从大到小排序
}

inline int get(int x){
    if(x==s[x])return x;
    return s[x]=get(s[x]);//路径压缩
}

int main(){
    n=qr(),m=qr();
    for(rg i=1;i<=m;++i)
        a[i].f=qr(),a[i].t=qr(),a[i].v=qr();
    sort(a+1,a+m+1,cmp); //贪心
    for(rg i=1;i<=n;++i)
        s[i]=i,s[i+n]=i+n; //初始化不能忘!!!
    for(rg i=1;i<=m;++i){
        rg x=a[i].f,y=a[i].t;
        if(get(x)==get(y)||get(x+n)==get(y+n)){
            f=a[i].v;break;//不能在同一*的仇人撞上了
        }
        s[s[x+n]]=s[y];
        s[s[x]]=s[y+n];//维护两罪犯在不同*的关系
    }printf("%d\n",f);
    return 0;
}

种类并查集其实你理解了,码量不高(如果算上快读等预处理的话......

一些对种类并查集的理解(血泪史)

代码中开数组是讲了不要开两个单独数组,因为两个独立的数组初始化时,赋的值都是 从 1 开始的,返回的是无区别的\(1\)\(n\)的下标,丢失了“A*”和“B*”的关系。将两数组并查集维护(不好实现)而且会因为有些值重复而让你 WA 到怀疑人生

其次,我们每次判断矛盾时,两个罪犯在A*和B*的位置都要判,而且是每个*单独判!这保证了算法的正确性!