【二分】【二分图染色】关押罪犯

Luogu P1525

题目：

将图中的点分成两部分，使得两部分中存在的边的最大值最小

题解：

分成两部分，额，第一反应应该就是二分图
带权怎么办？
我们考虑要求的是其中最大的最小，似乎是二分答案
于是，我们二分答案然后验证，要是边权>mid说明我们必须在二分图中给它连上，其他就可以不管，判一下是否是二分图，然后就AC啦qwq

#include<bits/stdc++.h>
using namespace std;
const int N=2e4+10,M=2e5+10;
int n,m;
int head[N],nex[M],to[M],val[M],tot;
void build(int u,int v,int w)
{
	tot++;nex[tot]=head[u];to[tot]=v;val[tot]=w;head[u]=tot;
}
int col[N],cnt,tim;
bool dfs(int u,int f)
{
	if(!col[u])col[u]=cnt;
	else {
		if(col[u]!=cnt)return 0;
		return 1;
	}
	bool tmp=1;
	for(int i=head[u];i;i=nex[i])
	{
		int v=to[i];if(v==f)continue;
		if(val[i]>tim)
		{
			cnt=col[u]^1;
			tmp&=dfs(v,u);
		}
	}return tmp;
}
bool check(int c)
{
	tim=c;
	for(int i=1;i<=n;i++)col[i]=0;
	for(int i=1;i<=n;i++)
	if(!col[i])
	{
		cnt=2;
		if(!dfs(i,i))return 0;
	}return 1;
}
int main()
{
	int ma=0;
	scanf("%d%d",&n,&m);
	for(int x,y,z,i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		build(x,y,z);build(y,x,z);
		ma=max(ma,z);
	}
	int l=0,r=ma,mid,ans;
	while(l<=r)
	{
		mid=(l+r)>>1; 
		if(check(mid))r=mid-1,ans=mid;
		else 		l=mid+1;
	}
	printf("%d",ans);
}