洛谷题目链接


输入

4 6
1 4 2534
2 3 3512
1 2 28351
1 3 6618
2 4 1805
3 4 12884

输出

3512

1.并查集

有意思的一道并查集的题，需要一些思维。
用并查集来维护，当a和b并到一起的时候说明他们两个在同一个监狱之中。
本题要求最大的仇恨值最小，所以用结构体存数据，先排序，仇恨值最大的排在前面，遍历这个结构体数组，遵循把敌人的敌人和我放在一个监狱的原则来add即可。其中要注意如果可以都不在一个监狱不发生冲突就输出0，所以循环要从1到m+1,这样到m+1的时候，数据：0，0，0，直接会check输出 0

注意：并查集必须先初始化！

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5+7;
const ll mod=2147483647;
ll n,m,w,b,c;
ll f[N],vis[N];
struct node
{
    ll x,y,z;
    bool operator<(const node &s)const
    {
        return z>s.z;
    }
}a[N];
inline void init()//并查集必须要初始化！
{
    for(int i=1;i<=n;++i)
        f[i]=i;
}
inline ll finds(ll x)
{
    return f[x]==x?x:f[x]=finds(f[x]);
}
inline void add(ll x,ll y)
{
    x=finds(x);
    y=finds(y);
    f[x]=y;
}
inline bool check(ll x,ll y)
{
    x=finds(x);
    y=finds(y);
    return x==y;
}
int main()
{
    scanf("%lld %lld",&n,&m);
    init();
    for(int i=1;i<=m;++i)
    {
        scanf("%lld %lld %lld",&a[i].x,&a[i].y,&a[i].z);
    }
    sort(a+1,a+1+m);
    for(int i=1;i<=m+1;++i)
    {
        if(check(a[i].x,a[i].y))
        {
            printf("%lld\n",a[i].z);
            break;
        }
        if(!vis[a[i].x])vis[a[i].x]=a[i].y;
        else add(vis[a[i].x],a[i].y);
        if(!vis[a[i].y])vis[a[i].y]=a[i].x;
        else add(vis[a[i].y],a[i].x);
    }
    return 0;
}

2.二分图

这道题总共有两个监狱，把一群人分到两个监狱里很明显就是一个二分图
那么就可以直接二分答案并用二分图判断即可
别人的代码和详解：
二分答案+二分图判断
有任何疑问欢迎评论哦虽然我真的很菜