欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

关押罪犯 二分 二分图 dfs

程序员文章站 2024-03-17 15:29:58
...

关押罪犯 二分 二分图 dfs
题解

#include<iostream>
#include<algorithm>
#include<cstring>
#define INF 0x1f1f1f1f
using namespace std;
#include<vector>

int n,m;

int  cot[20005];

vector<pair<int,int>> p[20005];

bool dfs(int x,int col,int limit)
{
	cot[x]=col;
//	cout<<"顶点"<<x<<"被染成"<<col<<"颜色"<<endl; 
	for(int i=0;i<p[x].size();i++)
	{
		if(p[x][i].second<=limit)
			continue;
		if(cot[p[x][i].first]==col)   //如果下一顶点已经被染成相同的颜色  return 0 
		{
//			cout<<col<<endl;
//			cout<<p[x][i].first<<"的颜色为"<<cot[p[x][i].first]<<endl;
//			cout<<"顶点"<<x<<"邻接点"<<p[x][i].first<<"有问题"<<endl ;
			return 0;
		}
			
		if(cot[p[x][i].first]==0 )     
		{
			if(!dfs(p[x][i].first,-col,limit))    //如果下一个顶点未被染色,且dfs失败  return 0 
			{
//				cout<<"顶点"<<x<<"邻接点"<<p[x][i].first<<"有问题"<<endl; 
				return 0; 
			}
				
		}
			 		
	}
	
	return 1;
}


bool get(int limit)
{
	memset(cot,0,sizeof(cot));
	for(int i=1;i<=n;i++)
	{
		if(cot[i]==0)
		{
			if(!dfs(i,2,limit))
			{
//				cout<<i<<endl;
				return 0;
			}
				
		}
	}
	return 1;
}


int main()
{
	cin>>n>>m;
	int x,y;
	int len;
	for(int i=0;i<m;i++)
	{
		scanf("%d%d%d",&x,&y,&len);
		p[x].push_back({y,len});
		p[y].push_back({x,len});
	}
	
	
	int l=0;           //二分  [,) 
	int r=1e9+1;
	
	
	int mid;
	while(l<r)
	{
		mid=(l+r)>>1;
		
		if(get(mid))
		{
			r=mid;
		}else {
			l=mid+1;
		}
	}
	if(l==0)
	{
		cout<<0;
	}else {
		cout<<l;
	}
	
	
	return 0;
}