并查集--解析关押罪犯问题（二）

在网上看到一道ACM竞赛题，很巧妙的运用了并查集解决了一个现实生活的问题，然而网上的解析太少，在这里贴出来我的思考：

题目：

S 城现有两座监狱，一共关押着N 名罪犯，编号分别为1~N。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久，如果客观条件具备则随时可能爆发冲突。我们用“怨气值”（一个正整数值）来表示某两名罪犯之间的仇恨程度，怨气值越大，则这两名罪犯之间的积怨越多。如果两名怨气值为c 的罪犯被关押在同一监狱，他们俩之间会发生摩擦，并造成影响力为c 的冲突事件。

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

在详细考察了 N 名罪犯间的矛盾关系后，警察局长觉得压力巨大。他准备将罪犯们在两座监狱内重新分配，以求产生的冲突事件影响力都较小，从而保住自己的乌纱帽。假设只要处于同一监狱内的某两个罪犯间有仇恨，那么他们一定会在每年的某个时候发生摩擦。那么，应如何分配罪犯，才能使 Z 市长看到的那个冲突事件的影响力最小？这个最小值是多少？

输入描述:
第一行为两个正整数N和M，分别表示罪犯的数目以及存在仇恨的罪犯对数。
接下来的M行每行为三个正整数aj，bj，cj，表示aj号和bj号罪犯之间存在仇恨，其怨气值为cj。
数据保证1≤aj＜bj≤N，0＜cj≤1,000,000,000，且每对罪犯组合只出现一次。
输出描述:
共1行，为Z市长看到的那个冲突事件的影响力。如果本年内监狱中未发生任何冲突事件，请输出0。
输入
4 6

1 4 2534

2 3 3512

1 2 28351

1 3 6618

2 4 1805

3 4 12884

输出
3512

解析题目：

这道题不多读几遍题目，还真不好理解。

它大致讲的是，只有2个监狱，有好多罪犯，两两间有怨气，两个监狱中会有两个罪犯间有一个最大怨气，问怎样分配罪犯能让这个最大怨气值最小。

正常思考：
我们先来分析：不用算法，正常人怎么想，一般是先把怨气值排序，我简单点列一下，假如说：

12代表对象1号和2号，10代表怨气值，排序后为：

12（10） 13（9） 14（8） 23（7） 24（6） 34（5）

排好序之后呢往两个监狱放罪犯，首先一定把12分开，所以A监狱1，B监狱2，然后13也要分开，A监狱1，B监狱变成23，然后14也要分开，所以A监狱1，B监狱变成234，注意到达临界点了，再往后最大值是23，但是23已经在一个监狱里了，不能把他们分开，否则23又要和1见面，导致怨气值增大，所以至此分配结束，最大怨气值是23的怨气值7。

算法思考：
然后想办法怎样利用并查集实现这样一种分配。并查集在上一篇文章中有总结：

牛奶：并查集详谈

并查集最主要的作用是查看两个数或者点或者集合是否有联系，以及如何将没有联系的两个集合合并到一起。但是这道题是分开到两个监狱，没有联系怎么办？

这里就需要寻找联系。通过前面的正常思考，你会发现，因为1和234怨气值都比较大，所以最后234尽管有怨气，但还是走到了一起，共同对付1。所以联系的地方就在于，敌人的敌人就是我们的朋友！2是1的敌人，3是1的敌人，所以最终23走到一起。当然前提是从最大怨气排序后进行考虑。

算法的解决办法就是开一个两倍大小的并查集，通过多出来的空间作为每一名罪犯的假想敌，间接的找到自己的盟友。

具体思想可以参考这个帖子：

并查集解决关押罪犯

通过多开出一个空间，就能让有联系的人划分到一个集合。

具体C++代码详解如下：

#include<bits/stdc++.h>//万能头文件
using namespace std;
const int N = 20005;//N,M是随意开辟的空间大小，用来存放罪犯数量和矛盾对数
const int M = 100005;
/*按照边权值排序，怒气大的边放在不同的监狱，然后使用并查集维护，当发现在同一集合的时候就终止条件
*/
//原因：
//1.参数里面那个const是为了不对原来的对象修改，另外这里用引用避免了对实参的拷贝，提高效率
//2.函数加上const后缀表示此函数不修改类成员变量，如果在函数里修改了则编译报错
//即表明输入参数是只读的，也表明函数本身也是只读的。用标准来讲，该函数是query。
struct node
{
    //u，v分别代表两个罪犯，w代表他们的怨气值
    int u,v,w;
    bool operator< (const node &a) const
    {
        return w > a.w;//代表重载从大到小排序，默认值是从小到大排序的
    }
} a[M]; ///按照怒气值排序 
int fa[N * 2];
int Find(int x)
{
    return x == fa[x] ? x : fa[x] = Find(fa[x]);
}

void Union(int x,int y)
{
    int fx = Find(x);
    int fy = Find(y);
    fa[fx] = fy;
}

int main()
{
    int n,m;//罪犯数和怨气有多少对
    while(cin >> n >> m)
    {
        for(int i = 0; i < m; i ++)
        {
            //输入每对罪犯的编号及怨气值
            cin >> a[i].u  >> a[i].v >>a[i].w;
        }
        for(int i = 1; i <= n; i ++)
        {
            //初始化两个空间，让下标都等于元素值
            fa[i] = i;///表示和i同监狱的人
            fa[i + n] = i + n;///表示和i不同监狱的人
        }
        sort(a,a + m);///按照怒气值排序

        int f1,f2,f3,f4,i;
        for( i = 0 ; i < m; i ++)
        {
            f1 = Find(a[i].u);
            f2 = Find(a[i].u + n);//另一个监狱f1的对手
            f3 = Find(a[i].v);
            f4 = Find(a[i].v + n);//另一个监狱f3的对手

            //从大到小往监狱放，当放到这里发现有矛盾的两个已经在前面实现了分放
            //跳出循环，结束操作，注意大概率不是最后一组怨气
            if(f1 == f3 || f2 == f4) break;
            ///代表不能在同一个监狱
            fa[f4] = f1;
            fa[f2] = f3;
        }
        //此时打印出最大怨气值，便是所要求的最小怨气值
        if(i <= m)
        {
            cout << a[i].w << endl;

        }
        else
        {
            cout << 0 << endl;
        }
    }
    return 0;
}