题目问的是最小值，我们仔细观察，这个是具有二分性质的
因此可以先考虑二分最小答案后进行check
对于check，其实就是个二分图，看能否把所有的怒气值大于答案的分别放在两边，而直接略过怒气值小的边
#include<bits/stdc++.h> using namespace std; const int N=2e5+10; int h[N],ne[N],e[N],w[N],idx; int color[N],n,m; void add(int a,int b,int c){ e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++; } int dfs(int u,int c,int x,int fa){ int i; color[u]=c; for(i=h[u];i!=-1;i=ne[i]){ int j=e[i]; if(j==fa) continue; if(w[i]<=x) continue; if(color[j]){ if(color[j]==c) return false; } else if(!color[j]){ if(!dfs(j,3-c,x,u)) return false; } } return true; } bool check(int x){ int i; memset(color,0,sizeof color); for(i=1;i<=n;i++){ if(!color[i]){ if(!dfs(i,1,x,-1)) return false; } } return true; } int main(){ memset(h,-1,sizeof h); int i; cin>>n>>m; while(m--){ int a,b,c; scanf("%d%d%d",&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; }