题解 | #[NOIP2010]关押罪犯#

思路

M 对互相仇恨的罪犯，我们按仇恨值从大到小排序，对于每一对互相仇恨的罪犯，我们要设法将他们分配在不同的监狱里，反正不能在同一监狱里

如果不可避免的在同一监狱了 也就是与我们的策略发生冲突了，那么此时的仇恨值就是答案
如果到最后都不曾发生冲突，那么答案是 0，因为此时：任意一对会冲突的罪犯 都不会位于同一个监狱(二分图)

不管是 从大到小排序 还是 分配在不同的监狱里，这一切都是为了保证：矛盾的最大值最小(题意要求)

法1：种类并查集：开二倍空间

令 x 表示 x 自身，x + n 表示 x 的敌人

Code

#include <bits/stdc++.h>

using namespace std;

const int N = 20010,M = 100010;

struct node{
    int a,b;
    int w;
    bool operator < (const node & x) const { return w > x.w ;}
}p[M]; 
int fa[N*2];
int n,m;

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

int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++) {
        int a,b,w;
        cin>>a>>b>>w;
        p[i]={a,b,w};
    }
    sort(p,p+m);
    for(int i=1;i<=2*n;i++) fa[i]=i;  // x表示本身，x+n表示x的敌人

   for(int i=0;i<m;i++){
       int a=p[i].a,b=p[i].b,w=p[i].w;
       if(find(a)==find(b)){  //a和b敌对，不应该在同一集合
           cout<<w<<endl;
           return 0;
       }
       else{  // 因为a、b敌对，所以a和b不应在同一集合，又b与其敌人不在同一集合
             // 所以a和b的敌人放一起
            // 同理：b和a的敌人放一起
            fa[find(a)]=find(b+n);
            fa[find(b)]=find(a+n);
       }
   }
    cout<<0<<endl;

    return 0;
}

法2：思想一样，但做法不同

因为只有两个集合，所以可以开辟数组 Enemy[i] = i, i 的敌人是 j
i 的敌人可能有很多，比如 j，k，z 等等，但是我们只需要记录一次就行，也是记录第一个枚举到的敌人就行

举例如下：1，2 敌对，1，3 敌对，1，4 敌对  （已经按权值排好序）
枚举到 1，2 时
enemy[1] 还未赋值，令 enemy[1] = 2
enemy[2] 还未赋值，令 enemy[2] = 1 

枚举到 1，3 时
enemy[1] 已有敌人：2，所以把 3 和 2 放到一个集合
enemy[3] 还未赋值，令 enemy[3] = 1

枚举到 1，4 时
enemy[1] 已有敌人：2，所以把 4 和 2 放到一个集合
enemy[4] 还未赋值，令 enemy[4] = 1

到此，2、3、4 在一个集合里，因为只有两个集合 所以 显然 1 在另一个集合里
因为运行到最后 都没有发生冲突，所以本样例的答案是 0，可验证：其与预期结果一致

Code

#include <bits/stdc++.h>

using namespace std;

const int N = 20010,M = 100010;

struct node{
    int a,b;
    int w;
    bool operator < (const node & x) const { return w > x.w ;}
}p[M]; 
int fa[N];
int Enemy[N];
int n,m;

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

int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++) {
        int a,b,w;
        cin>>a>>b>>w;
        p[i]={a,b,w};
    }
    sort(p,p+m);

    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=0;i<=m;i++){
        int a=p[i].a,b=p[i].b,w=p[i].w;
        if(find(a)==find(b)) {
            cout<<w<<endl;   // 冲突不可避免
            return 0;
        }
        else{  // 设法避免冲突：敌人的敌人是朋友
            if(!Enemy[a]) Enemy[a]=b;
            else fa[find(b)]=find(Enemy[a]);
            if(!Enemy[b]) Enemy[b]=a;
            else fa[find(a)]=find(Enemy[b]);
        }
    }
    cout<<0<<endl;  // 冲突可避免

    return 0;
}