关押罪犯（并查集）

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

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

在详细考察了 N 名罪犯间的矛盾关系后，警察局长觉得压力巨大。他准备将罪犯们在两座监狱内重新分配，以求产生的冲突事件影响力都较小，从而保住自己的乌纱帽。假设只要处于同一监狱内的某两个罪犯间有仇恨，那么他们一定会在每年的某个时候发生摩擦。那么，应如何分配罪犯，才能使 Z 市长看到的那个冲突事件的影响力最小？这个最小值是多少？
分析
我们要求冲突值最小，我们按罪犯之前的冲突值从大到小排序，能安排在不同监狱就安排在不同监狱 这样他们之间不会发生冲突
然后如果当前的两个罪犯无法避免只能安排到同一监狱，那么最小值就是他们之间的冲突值
我们本着敌人的敌人是朋友的原则 记录每个人的敌人，然后把敌人的敌人安排在同一监狱

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include<bitset>
#include <vector>
#include <iomanip>
#include <sstream>
#pragma GCC optimize(2)
#define UpMing main
#define re register
#define Accept return 0;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define mst(x, a) memset(x,a,sizeof(x))
#define lowbit(x) ((x)&(-(x)))
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
const int inf =0x3f3f3f3f;
const ll  inf2 =0x3f3f3f3f3f3f3f;
const int maxn=1e6+10;
const ll mod = 998244353;
const int N =1e6+10;
inline ll read() {
    ll  x=0;
    bool f=0;
    char ch=getchar();
    while (ch<'0'||'9'<ch)    f|=ch=='-', ch=getchar();
    while ('0'<=ch && ch<='9')
        x=x*10+ch-'0',ch=getchar();
    return f?-x:x;
}
void out(ll x) {
    int stackk[20];
    if(x<0) {
        putchar('-');
        x=-x;
    }
    if(!x) {
        putchar('0');
        return;
    }
    int top=0;
    while(x) stackk[++top]=x%10,x/=10;
    while(top) putchar(stackk[top--]+'0');
}
ll n,m,f[maxn],b[maxn];
struct wmy {
    ll u,v,w;
} a[maxn];
ll find(ll x) {
    if(f[x]==x) return x;
    return f[x]=find(f[x]);
}
bool cmp(wmy x,wmy t) {
    return x.w>t.w;
}
void c(ll x,ll y) {
    ll dx=find(x);
    ll dy=find(y);
    if(dx!=dy) f[dx]=dy;
}
int UpMing() {
    n=read();
    for(int i=1 ; i<=n ; i++) f[i]=i;
    m=read();
    ll sum=0;
    for(int i=1 ; i<=m ; i++)
        a[i].u=read(),a[i].v=read(),a[i].w=read();
    sort(a+1,a+1+m,cmp);
    for(int i=1 ; i<=m ; i++) {
        // 此时的冲突已经不可避免了
        if(find(a[i].u)==find(a[i].v)) {
            out(a[i].w);
            return 0;
        }
        ll u=a[i].u;
        ll v=a[i].v;
        // 敌人的敌人就是朋友
        if(b[u]==0) b[u]=v;
        else c(b[u],v);
        if(b[v]==0) b[v]=u;
        else c(b[v],u);
    }

    out(sum);
    Accept;
}