莫欺少年穷，修魔之旅在这开始—>算法提高课题解

思路：

1. 二分答案区间
2. 判断大于mid的边是否能够染色成功
3. 如果成功说明仇恨值小于等于 mid，否则仇恨值大于 mid

可参考： 染色法判定二分图

#include<bits/stdc++.h>

using namespace std;

const int N = 20010, M = 200010;

int n,m;
int h[N],e[M],w[M],ne[M],idx;
int color[N];

void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

bool dfs(int u,int c,int mid)
{
    color[u]=c;

    for(int i=h[u];~i;i=ne[i])
    {
        //只判断大于mid的边
        if(w[i]<=mid) continue;

        int j=e[i];
        if(!color[j])
        {
            if(!dfs(j,3-c,mid)) return false;
        }
        else if(color[j]==c) return false; 
    }

    return true;
}

bool check(int mid)
{
    //别忘了初始化哟
    memset(color,0,sizeof color);

    for(int i=1;i<=n;i++) 
        if(!color[i])
            if(!dfs(i,1,mid))
                return false;

    return true;
}

int main()
{
    cin>>n>>m;

    memset(h,-1,sizeof h);

    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }

    //二分答案
    int l=0,r=1e9;
    while(l<r)
    {
        int mid=l+r>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
    }

    cout<<l<<endl;

    return 0;
}