《种类并查集》

对于不能一个并查集不够用了，还需要另一个并查集，但是不能开两个数组作为两个并查集，因为两个并查集之间不能有明确的区分

以样例说明：

贪心思路：

很容易便能想到，我们要使怒气值大的一对人尽量不在同一间监狱里。也就是说，我们要优先考虑怒气值最大的两个人，然后是次大，以此类推。这一想法很容易证明，即用交换法。

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstring>
 4 using namespace std;
 5 const int N = 200000;
 6 // a 表示并查集
 7 // hate表示两个犯人之间的关系
 8 struct node
 9 {
10     int l, r, w;
11 } hate[N];
12 int a[N * 2];
13 int n, m;
14 //返回x的祖先是谁
15 int find(int x)
16 {
17     if (a[x] != x)
18         a[x] = find(a[x]);
19     return a[x];
20 }
21 //合并,本题即关进相同监狱
22 void merge(int x, int h)
23 {
24     a[find(h)] = find(x + n);
25     a[find(h + n)] = find(x);
26 }
27 int main()
28 {
29     cin >> n >> m;
30     //初始化并查集
31     for (int i = 1; i <= n * 2; i++)
32         a[i] = i;
33     for (int i = 1; i <= m; i++)
34         scanf("%d%d%d", &hate[i].l, &hate[i].r, &hate[i].w);
35     sort(hate + 1, hate + m + 1, [](struct node a, struct node b)
36          { return a.w > b.w; });
37     //这道题绝对不能指明清楚的监狱关系
38     //即不能说犯人1进A监狱,犯人2进B监狱,这样明确的
39     //要不论A,B监狱怎么变化都不影响影响力
40 
41     //!!!注意我们规定:有共同祖先说明两者在同一个监狱
42 
43     //如果对于犯人i,其有两个分身，一个是i,一个是i+n
44     //当i分监狱时,如果i进A监狱，i+n就要进B监狱
45     //如果i进B监狱，i+n就要进A监狱,即i,i+n是永远不会在同一个监狱
46     //并且A,B监狱不管如何变换,i与i+n的关系不会变
47 
48     //到后面如果犯人i+k与犯人i有排在更前面的影响力
49     //首先判断犯人i+k与犯人i在贪心下是否被强制在一个监狱
50     //即判断if(find(a[i+k])==find(a[i])),即判断是否是共同祖先
51     //如果是则可以退出整个算法,i+k与i之间的影响力就是最大影响力中的最小了;
52     //如果不在则进行如下一步:
53 
54     //则i+k要与i分开监狱
55     //即要将i+k与i+n合并,因为i与i+n永远不会在同一个监狱，这是规定
56     //同时i与i+k+n合并
57     //即a[find(i+k)]=find(i+n); a[find(i+k+n)]=find(i);
58 
59     //对于下一个关系重复上述步骤
60     int res = 0;
61     for (int i = 1; i <= m; i++)
62     {
63         auto t = hate[i];
64         if (find(t.l) == find(t.r))
65         {
66             res = t.w;
67             break;
68         }
69         merge(t.l, t.r);
70     }
71     cout << res;
72 }