原题链接
题意：
将所有点分成两组，使得每一组内最大边权尽可能小。
思路：
建图过程为把罪犯看做点，把罪犯之间的仇恨看做是边，怨气值为边权。
最大值最小化可以二分求解，那么如何check呢。
我们可以二分最大边权，将大于等于最大边权的边放在一组，小于最大边权的边放在一组，染色法判断是否为二分图即可。
代码：
#include<bits/stdc++.h> using namespace std; const int maxn=1e6+7; int h[maxn],idx; struct node{ int e,ne,w; }edge[maxn]; void add(int u,int v,int w){ edge[idx].e=v,edge[idx].w=w,edge[idx].ne=h[u],h[u]=idx++; } int n,m; int col[maxn]; bool dfs(int u,int c,int limit){ col[u]=c; for(int i=h[u];~i;i=edge[i].ne){ int j=edge[i].e; if(edge[i].w<=limit) continue; if(col[j]){ if(col[j]==c) return 0; } else if(!dfs(j,3-c,limit)) return 0; } return 1; } bool check(int limit){ memset(col,0,sizeof col); for(int i=1;i<=n;i++) if(!col[i]){ if(!dfs(i,1,limit)) return 0; } return 1; } int main(){ memset(h,-1,sizeof h); cin>>n>>m; for(int i=1;i<=m;i++){ int u,v,w; cin>>u>>v>>w; add(u,v,w);add(v,u,w); } int l=0,r=1e9,res; while(l<=r){ int mid=l+r >>1; if(check(mid)) r=mid-1,res=mid; else l=mid+1; } cout<<res<<endl; return 0; }
