RT，WA了3,7,8,9

就是二分+黑白染色，输出出来答案小了，小的不多，目测二分没问题。

// Problem: P1525 [NOIP2010 提高组] 关押罪犯
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1525
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define M 200005
#define mid ((l+r)/2)
int n,l,r,m,U,V,W,ans=10000008,vis[M]; //vis+记录颜色的功能,为了判断有没有dfs过所以颜色是1/2
struct node
{int s,t,v;}rd[M];//存边
vector<int>road[M]; //vector存图
map<int,int>mp,fmp; //离散化用
bool cmp(node A,node B) {return A.v<B.v;} //排序用
int dfsl(int x)
{
	for(int i=0;i<road[x].size();i++) if(vis[road[x][i]]==vis[x]) return 1; //如果有染色冲突
	for(int i=0;i<road[x].size();i++) {
	 if(!vis[road[x][i]])
	  {
	  	vis[road[x][i]]=3-vis[x];
	  	if(dfsl(road[x][i])) return 1;
	  }
	}
	//上面七行往下dfs,如果有不能黑白染色的就返回不可以
	return 0;
}
bool check(int x)
{
	memset(vis,0,sizeof(vis)); int rrt;
	for(int i=1;i<=n;i++) road[i].clear();
	//上面两行初始化
	for(int i=1;i<=m;i++)
	{
	    if(rd[i].v>x)
		{
			road[rd[i].s].push_back(rd[i].t);
			road[rd[i].t].push_back(rd[i].s);
			rrt=rd[i].s;
		}
	}
	//上面九行建图
	vis[rrt]=1; if(dfsl(rrt)) return 0; //如果这玩意不能黑白染色(不能黑白染色的返回是1不是0)
	return (ans=min(ans,x),1); //返回+更新答案
}
int main()
{
	cin>>n>>m,r=m;
	for(int i=1;i<=m;i++)
	{
		cin>>U>>V>>W;
		rd[i].s=min(U,V),rd[i].t=max(U,V),rd[i].v=W;
	}
	sort(rd+1,rd+m+1,cmp);
	for(int i=1;i<=m;i++) mp[rd[i].v]=i,fmp[i]=rd[i].v;
	for(int i=1;i<=m;i++) rd[i].v=mp[rd[i].v];
	//上面三行离散化
	while(l+2<=r) 
	{
		if(check(mid)) r=mid-1;
		else l=mid+1;
	}
	//上面五行二分
	for(int i=l;i<=r;i++) check(i);
	cout<<fmp[ans]<<endl;
	return 0;
}