染色法+二分的应用
要提高找到问题本质并抽象成已经学过的模型的能力
#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;
}