题解 P1525 【关押罪犯】

· · 题解

主体思路：

  1. 读入。
  2. 排序（因为有权值）。
  3. 双倍存储并查集（A 与 B 有矛盾，将 A 与 B + N 归为一组，B 与 A+N 归为一组，若 A 与 B 在同一组或 A+N 与 B+N 在同一组，则无法避免，输出当前冲突值）。

    代码：

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
struct bcj{                    //并查集
    int len;                   //长度
    int q[40005];              //存储，q[i]代表i的老大
    void init(int lenn){       //初始化一个长度为lenn的并查集
        len=lenn;
        for(int i=1;i<=len;i++)
            q[i]=i;
    }
    int Find(int t){           //找t的顶级老大
        if(q[t]==t) return t;
        else return Find(q[t]);
    }
    void in(int a,int w){      //将a及a的老大团加入w团
        if(q[a]!=a) in(q[a],w); 
        q[a]=w;
    } 
    void add(int a,int b){     //合并a和b所在老大团
        int a_1=Find(a),b_1=Find(b);
        q[a_1]=b_1;
        in(a,b_1);
    }
    int num(){                 //求老大团数
        int ans;
        for(int i=1;i<=len;i++)
            if(q[i]==i)
                ans++;
        return ans;
    }
    bool same(int a,int b){    //a和b是否在一个集合中
        int a_1=Find(a),b_1=Find(b);
        return a_1==b_1;
    }
}a;
struct Pair{
    int a,b,c;
}p[100005];
bool cmp(Pair q,Pair w){
    return q.c>w.c;
}
int n,m;
int main(){
    scanf("%d %d",&n,&m);
    a.init(n*2);
    for(int i=1;i<=m;i++)
        scanf("%d %d %d",&p[i].a,&p[i].b,&p[i].c);
    sort(p+1,p+m+1,cmp);
    for(int i=1;i<=m;i++){
        if(!a.same(p[i].a,p[i].b) && !a.same(p[i].a+n,p[i].b+n)){
            a.add(p[i].a,p[i].b+n);a.add(p[i].a+n,p[i].b);
        }else {
            printf("%d",p[i].c);
            return 0;
        }
    }
    printf("0");

    return 0;
}

码风不好，还请见谅。