由于两座监狱之间的边产生的冲突值可以被忽略, 所以只要让大的边的两侧的罪犯在两座监狱即可
因而想到二分图,
二分最大的怨气值, 然后利用大于怨气值的边来建图, 因为小于该值的边都不会在监狱内部产生更大的冲突
#include <iostream>
#include <cstring>
#include <algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int N=2e4+10;
const int M=1e5+10;
struct Edge{
int u,v,w;
} edge[M<<1];
int n,m;
int idx=0,h[N],w[M<<1],e[M<<1],ne[M<<1];
int color[N]; // -1 未染色 0/1 染色
int l=0,r=-1;
inline void add(int x,int y,int z){
e[++idx]=y, w[idx]=z, ne[idx]=h[x], h[x]=idx;
}
bool dfs(int p,int c){
// 默认可以染
color[p]=c;
for(int i=h[p];i;i=ne[i]){
int j=e[i];
if(color[j]==-1){
if(!dfs(j,!c)) return 0;
}else if(color[j]==c) return 0;
}
return 1;
}
bool check(int x){
idx=0;
memset(h,0,sizeof h);
memset(color,-1,sizeof color);
rep(i,1,m) if(edge[i].w>x)
add(edge[i].u,edge[i].v,edge[i].w),
add(edge[i].v,edge[i].u,edge[i].w);
bool flag=1;
rep(i,1,n){
if(color[i]==-1){
if(!dfs(i,0)){
flag=0;
break;
}
}
}
return flag;
}
int main(){
ios::sync_with_stdio(0), cin.tie(0);
cin>>n>>m;
rep(i,1,m){
int x,y,z; cin>>x>>y>>z;
edge[i]={x,y,z}, r=max(r,z);
}
while(l<r){
int mid=(l+r)>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
cout<<l;
return 0;
}