洛谷1525 关押罪犯

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
struct edge{
	int v,w,next;
}Edge[200005];
int n,m,col[20005],data[200005];//这是一个非常坑的地方，因为是无向图
int head[20005],cnt;//要建两条有向边，所以总边要乘2！
int l,r,mid,Max;
bool book[20005];
inline void AddEdge(int u,int v,int w){//邻接链表存边
	cnt++;
	Edge[cnt].v=v;
	Edge[cnt].w=w;
	Edge[cnt].next=head[u];
	head[u]=cnt;
	return;
}
bool dfs(int u,int color){//基本上二分图染色都可以参照这个模板
	if (book[u]) return col[u]==color;//如果访问过，那么看看染得色会不会冲突
	book[u]=true;
	col[u]=color;
	bool flag=true;
	for (int i=head[u];i!=0&&flag;i=Edge[i].next){
		int v=Edge[i].v;
		if (Edge[i].w<=Max) continue;//如果比枚举的最大边Max小，可以不用管它，即把它暂时
		flag=dfs(v,1-color);//放在原来的联通块中
	}
	return flag;
}
inline bool Colored(){
	memset(book,false,sizeof (book));//不要忘了初始化
	memset(col,0,sizeof (col));
	Max=data[mid];
	for (int i=1;i<=n;i++){
		if (book[i]) continue;
		if (!dfs(i,0)) return false;//如果冲突直接退出
	}
	return true;
}
int main(){
	int u,v,w;
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;i++){
		scanf("%d%d%d",&u,&v,&w);
		data[i]=w;
		AddEdge(u,v,w);
		AddEdge(v,u,w);
	}
	sort (data+1,data+m+1);//我这里是从边的大小二分，所以要排序
	l=0;
	r=m;
	while (l<r){
		mid=(l+r)>>1;
		if (Colored()) r=mid;//二分中的r=mid还是r=mid+1等问题一定要想清楚！
		else l=mid+1;
	}
	printf ("%d\n",data[l]);
	return 0;
}