(二分，染色法判断二分图) $O((N+M)logC)$

从所有仇恨值中二分出答案可能的仇恨的值，对于每个二分出的仇恨值判断大于这个仇恨值值的边是否是二分图，最后求出最小仇恨值

时间复杂度 $O((N+M)logC)$

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=20010,M=200010;
int e[M],ne[M],h[N],w[M],idx,n,m,limit,minlimit,W[100010];
int color[N];
void add(int a,int b,int c)
{
    e[idx]=b;
    ne[idx]=h[a];
    w[idx]=c;
    h[a]=idx++;
}
bool dfs(int v,int c)
{
    color[v]=c;
    for(int i=h[v];i!=-1;i=ne[i])
    {
        if(w[i]<=limit)
            continue;
        int j=e[i];
        if(!color[j])
        {
            if (!dfs(j,3-c))
                return false;
        }
        else if(color[j]==c)
            return false;
    }
    return true;
}
bool check()
{
    bool flag=true;
    memset(color,0,sizeof color);
    for(int i=1;i<=n;i++)
    {
        if(!color[i])
            if(!dfs(i,1))
            {
                flag=false;
                break;
            }
    }
    return flag;
}
int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
        W[i]=c;
    }
    sort(W,W+m);
    minlimit=W[m-1];
    int l=0,r=m-1;
    while(l<=r)
    {
        int mid=(l+r)/2;
        limit=W[mid];
        if(check())
            {
                r=mid-1;
                minlimit=limit;
            }
        else
            l=mid+1;
    }
    if(r==-1)
        minlimit=0;
    cout<<minlimit<<"\n";
    return 0;
}