染色法+二分的应用

要提高找到问题本质并抽象成已经学过的模型的能力

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2e5+10;

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

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 x){
    color[u]=c;

    for(int i=h[u];i;i=ne[i]){
        if(w[i]<=x)continue;
        int j = e[i];
        if(!color[j]){
            if(!dfs(j,3-c,x))return false;
        }else if(color[j]==c)return false;
    }
    return true;
}

bool check(int x){
    memset(color,0,sizeof color);
    for(int i=1;i<=n;i++){
        if(!color[i])
            if(!dfs(i,1,x))return false;
    }
    return true;
}

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

    for(int i=0;i<m;i++){
        int a,b,c;scanf("%d%d%d",&a,&b,&c);
        add(a,b,c),add(b,a,c);
    }

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

    cout<<r<<endl;//大于r的满足二分图，小于不满足，r则是最小值的最大值

    return 0;
}