Problem Description
S 城现有两座*，一共关押着N 名罪犯，编号分别为1~N。他们之间的关系自然也极
不和谐。很多罪犯之间甚至积怨已久，如果客观条件具备则随时可能爆发冲突。我们用“怨
气值”（一个正整数值）来表示某两名罪犯之间的仇恨程度，怨气值越大，则这两名罪犯之
间的积怨越多。如果两名怨气值为c 的罪犯被关押在同一*，他们俩之间会发生摩擦，并
造成影响力为c 的冲突事件。
每年年末，警察局会将本年内*中的所有冲突事件按影响力从大到小排成一个列表，
然后上报到S 城Z 市长那里。公务繁忙的Z 市长只会去看列表中的第一个事件的影响力，
如果影响很坏，他就会考虑撤换警察局长。
在详细考察了N 名罪犯间的矛盾关系后，警察局长觉得压力巨大。他准备将罪犯们在
两座*内重新分配，以求产生的冲突事件影响力都较小，从而保住自己的乌纱帽。假设只
要处于同一*内的某两个罪犯间有仇恨，那么他们一定会在每年的某个时候发生摩擦。那
么，应如何分配罪犯，才能使Z 市长看到的那个冲突事件的影响力最小？这个最小值是少？
Input
第一行为两个正整数N 和M，分别表示罪犯的数目以及存在仇恨的罪犯对数。
接下来的M 行每行为三个正整数aj，bj，cj，表示aj 号和bj 号罪犯之间存在仇恨，其怨气值为cj。数据保证，且每对罪犯组合只出现一次。
output
共1 行，为Z 市长看到的那个冲突事件的影响力。如果本年内*
中未发生任何冲突事件，请输出0。
思路：因为答案具有单调性，所以可以二分答案，然后把怒气值大于mid的两名罪犯之间连边，检验是否为二分图即可
#include<bits/stdc++.h>
using namespace std;
const int N = ; int head[N],now;
struct edges{
int to,next;
}edge[N<<];
void add(int u,int v){ edge[++now] = {v, head[u]}; head[u] = now;} int n,m,mx,col[N];
bool flag;
struct input{
int x,y,z;
}inp[N]; void dfs(int x,int color){
col[x] = color;
for(int i = head[x]; i; i = edge[i].next){
int v = edge[i].to;
if(!col[v]) dfs(v, - color);
else if(!flag || col[v] == color){
flag = ;
return ;
}
}
} bool che(int x){
memset(edge,,sizeof(edge));
memset(head,,sizeof(head)); now = ;
memset(col,,sizeof(col)); flag = ;
for(int i = x+; i <= m; i++)
add(inp[i].x,inp[i].y), add(inp[i].y,inp[i].x);
for(int i = ; i <= n ;i++){
if(!flag) break;
else if(!col[i]) dfs(i,);
}
return flag;
} bool cmp(input x,input y){ return x.z<y.z; } int main(){
scanf("%d%d",&n,&m);
int x,y,z;
for(int i = ; i <= m; i++){
scanf("%d%d%d",&x,&y,&z);
inp[i] = {x,y,z};
}
sort(inp+,inp+m+,cmp);
int l = , r = m, ans;
while(l <= r){
int mid = l + r >> ;
if(che(mid)) ans = mid,r = mid - ;
else l = mid + ;
}
printf("%d\n",inp[ans].z);
return ;
}