关押罪犯

题目链接：https://ac.nowcoder.com/acm/problem/16591

思路

见此题的视频讲解：https://www.bilibili.com/video/BV1nz411b75c

代码

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define PI acos(-1)
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const ll maxn = 1e6+10;
double eps = 1e-8;

int N,M;
struct node{
    int a,b,c;
    bool operator < (const node& o) const{
        return c>o.c;
    }
}arr[maxn];
int fa[maxn];
int find(int x){
    return fa[x] == x?x:fa[x] = find(fa[x]);
}
void join(int x,int y){
    int fx = find(x),fy = find(y);
    if(fx != fy) fa[fx] = fy;
}

int main(){
    ios;
    cin>>N>>M;
    for(int i = 1;i<=2*N;i++) fa[i] = i;
    for(int i = 1;i<=M;i++){
        int a,b,c;cin>>a>>b>>c;
        arr[i] = {a,b,c};
    }
    sort(arr+1,arr+M+1);
    for(int i = 1;i<=M;i++){
        int a,b,c;
        a = arr[i].a,b = arr[i].b,c=arr[i].c;
        if(find(a) == find(b)){
            cout<<c<<endl;
            return 0;
        }else{
            join(a,b+N);
            join(a+N,b);
        }
    }
    cout<<0<<endl;
    return 0;
}