记录编号	584007	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010]关押罪犯	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.118 s
提交时间	2023-10-26 17:32:45	内存使用	3.12 MiB

#include <bits/stdc++.h> 
using namespace std;
//二分+二分图 
const int N = 2e4+10,M = 1e5+10;
struct made{
	int ver,nx;
}e[M];
int hd[N],tot,v[N];
void add(int x,int y){
	tot++;
	e[tot].nx = hd[x],e[tot].ver = y,hd[x] = tot; 
} 
void re(){
	tot = 0;
	memset(hd,0,sizeof(hd));
	memset(e,0,sizeof(e));
	memset(v,0,sizeof(v));
}

int n,m;bool f;
struct node{
	int x,y,z;
}a[M];
bool dfs(int x,int col){
	v[x] = col;
	for(int i = hd[x];i;i = e[i].nx){
		int y = e[i].ver;
		if(!v[y])dfs(y,3-col);
		else if(v[y] == col)f = 0;
	}
}
bool check(int x){
	re();
	for(int i = 1;i <= m;i++)
		if(a[i].z > x){
		    add(a[i].x,a[i].y);
		    add(a[i].y,a[i].x);//建双边！！！！！！ 
		}//任意两个罪犯影响力大于mid 
	f = 1;
	for(int i = 1;i <= n;i++)
		if(!v[i])dfs(i,1);
	return f;
}
int main(){
	freopen("prison1.in","r",stdin);
	freopen("prison1.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i = 1;i <= m;i++)
		scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
    int l = 0,r = 1e9;
    while(l < r){
    	int mid = l + r >> 1;
    	if(check(mid))r = mid;
    	else l = mid + 1;
    }
    printf("%d\n",l);
	
	return 0;
	
}