种类并查集

题目描述

城现有两座监狱，一共关押着罪犯。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久，如果客观条件具备则随时可能爆发冲突。我们用“怨气值”（一个正整数值）来表示某两名罪犯之间的仇恨程度，怨气值越大，则这两名罪犯之间的积怨越多。如果两名怨气值为的罪犯被关押在同一监狱，他们俩之间会发生摩擦，并造成影响力为的冲突事件。
每年年末，警察局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表，然后上报到S 城Z 市长那里。公务繁忙的Z 市长只会去看列表中的第一个事件的影响力，如果影响很坏，他就会考虑撤换警察局长。
在详细考察了罪犯间的矛盾关系后，警察局长觉得压力巨大。他准备将罪犯们在两座监狱内重新分配，以求产生的冲突事件影响力都较小，从而保住自己的乌纱帽。假设只要处于同一监狱内的某两个罪犯间有仇恨，那么他们一定会在每年的某个时候发生摩擦。
那么，应如何分配罪犯，才能使Z市长看到的那个冲突事件的影响力最小？这个最小值是多少？
输入格式
每行中两个数之间用一个空格隔开。第一行为两个正整数，分别表示罪犯的数目以及存在仇恨的罪犯对数。接下来的MM行每行为三个正整数，表示号和号罪犯之间存在仇恨，其怨气值为。数据保证，且每对罪犯组合只出现一次。
输出格式
共1行，为Z市长看到的那个冲突事件的影响力。如果本年内监狱中未发生任何冲突事件，请输出0。

其实很容易想到，这里可以贪心，把所有矛盾关系从大到小排个序，然后尽可能地把矛盾大的犯人关到不同的监狱里，直到不能这么做为止。这看上去可以用并查集维护，但是有一个问题：我们得到的信息，不是哪些人应该在相同的监狱，而是哪些人应该在不同的监狱。这怎么处理呢？这个题其实有很多做法，但这里，我们介绍使用种类并查集的做法。

种类并查集可以维护敌人的敌人是朋友这样的关系，这种说法不够准确，较为本质地说，种类并查集（包括普通并查集）维护的是一种循环对称的关系

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

const int N = 20010*2, M = 100010;
int p[N];
int enemy[N];//tag the enemy of x

struct Edge{
    int a,b,w;
    bool operator<(const Edge& t) const {
        return w>t.w;
    }
}e[M];

int n, m;

int find(int x) {
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}


int main() {
    cin>>n>>m;
    for(int i=0; i<m; ++i) {
        cin>>e[i].a>>e[i].b>>e[i].w;
    }
    for(int i=0; i<N; ++i) p[i] = i;
    sort(e,e+m);
    int res=0;
    for(int i=0; i<m; ++i) {
        int a=e[i].a, b=e[i].b;
        if(find(a) == find(b) || find(a+n) == find(b+n)) {//in the same set and is enemy
            res=e[i].w;
            break;
        } else {//is enemy and not in the same set
            p[find(a)] = find(b+n);
            p[find(b)] = find(a+n);
        }
    }
    printf("%d", res);
    return 0;
}

所以如果是三个及以上的集合，只要每个集合都是等价的，且集合间的每个关系都是等价的，就能够用种类并查集进行维护。例如下面这道题：

题目描述

动物王国中有三类动物 A,B,C，这三类动物的食物链构成了有趣的环形。A 吃 B，B
吃 C，C 吃 A。
现有 N 个动物，以 1 － N 编号。每个动物都是 A,B,C 中的一种，但是我们并不知道
它到底是哪一种。
有人用两种说法对这 N 个动物所构成的食物链关系进行描述：
第一种说法是“1 X Y”，表示 X 和 Y 是同类。
第二种说法是“2 X Y”，表示 X 吃 Y 。
此人对 N 个动物，用上述两种说法，一句接一句地说出 K 句话，这 K 句话有的是真
的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。
• 当前的话与前面的某些真的话冲突，就是假话
• 当前的话中 X 或 Y 比 N 大，就是假话
• 当前的话表示 X 吃 X，就是假话
你的任务是根据给定的 N 和 K 句话，输出假话的总数。
输入格式
从 http://eat.in 中输入数据
第一行两个整数，N，K，表示有 N 个动物，K 句话。
第二行开始每行一句话（按照题目要求，见样例）
输出格式
输出到 eat.out 中
一行，一个整数，表示假话的总数。

我们会发现，A、B、C三个种群天然地符合用种类并查集维护的要求。

于是我们可以用一个三倍大小的并查集进行维护，用i+n表示i的捕食对象，而i+2n表示i的天敌。

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

const int N = 100010 * 3;

int p[N];

inline int read(){
    int ret=0,f=1;char c;
    while((c=getchar())<'0'||c>'9')if(c=='-')f=-1;
    while(c>='0'&&c<='9')ret=ret*10+(c-'0'),c=getchar();
    return ret*f;
}

int find(int x) {
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}

int n, k;
//规定1吃2，2吃3，3吃1

int main()
{
    n=read(), k=read();
    int op, x, y;
    for(int i=0; i<N; ++i) p[i] = i;
    int res = 0;
    while(k--) {
        op=read(),x=read(),y=read();
        if(x > n || y > n) {
            res++;
            continue;
        } 
        if(op == 1) {//x,y是同类
            if(find(x) == find(y+n) || find(y) == find(x+n)) {//x吃y || y吃x
                res++;
            }else {
                p[find(x)] = find(y);
                p[find(x+n)] = find(y+n);
                p[find(x+n+n)] = find(y+n+n);
            }
        }else {//x吃y
            if(find(x) == find(y) || find(y) == find(x+n)) {//x=y || y吃x
                res++;
            } else {
                p[find(x)] = find(y+n);
                p[find(x+n)] = find(y+n+n);
                p[find(x+n+n)] = find(y);
            }
        }
    }
    cout<<res;
    return 0;
}

种类并查集

题目描述

题目描述

推荐阅读