判定

• 一张图是二分图，当且仅当图中不存在奇环。
• 如果两个集合中的点分别染成黑色和白色，可以发现二分图中的每一条边都一定是连接一个黑色点和一个白色点。

例题：关押罪犯

#include<queue>
#include<cstdio>
#include<iostream>
#include<algorithm>
#define cs const
#define mid (l+r>>1)
#define il inline
#define ri register
#define pc(i) putchar(i)
using namespace std;
cs int N=2e4+3,M=1e5+3,inf=0x3f3f3f3f;
int head[N],n,m,tot,l=1,r,color[N];
struct node{int to,nxt,w;}edge[M<<1];
il void read(int &as)
{
	int f=1;char ch=getchar();as=0;
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') as=(as<<3)+(as<<1)+(ch^48),ch=getchar();as*=f;
}
il void wt(int x){if(x<0) x=-x,pc('-');if(x>9) wt(x/10);pc(x%10|48);}
il void add(cs int u,cs int v,cs int w){edge[++tot]=(node){v,head[u],w},head[u]=tot;}
il bool bfs(cs int x)//验证是否可以构成二分图
{
	queue<int>q;
	for(ri int i(1);i<=n;++i) color[i]=0;
	for(ri int o(1);o<=n;++o)
	{
		if(color[o]) continue;
		q.push(o),color[o]=1;
		while(!q.empty())
		{
			int u=q.front();q.pop();
			for(ri int i(head[u]);i;i=edge[i].nxt)
				if(edge[i].w>=x)
					if(!color[edge[i].to]) 
						q.push(edge[i].to),color[edge[i].to]=-color[u];
					else if(color[edge[i].to]==color[u]) return false;
		}
	}
	return true;
}
int main()
{
	read(n),read(m);
	if(m==1) return puts("0"),0;//特判只有一个人的情况，此时没有怨气值
	for(ri int i(1),u,v,w;i<=m;++i)
		read(u),read(v),read(w),r=r>w?r:w,add(u,v,w),add(v,u,w);
	r++;
	while(r>l+1)//二分答案
		if(bfs(mid)) r=mid; else l=mid;
	wt(l);
	return 0;
}