[Acwing] 257. 关押罪犯 二分+二分图染色法判定

前言

传送门 :

思路

回顾 : 二分图 : 能被分成两个集合,并且边在都在集合之间,单个集合之内没有相连的边

因为题目中有 最大的怒气值最小 的意味,我们考虑使用二分怒气值

我们考虑将 所有大于 m i d mid mid的边 放在集合中间, 也即是我们考虑将 这个图分成两半

如果 中间的边都大于 m i d mid mid 而集合内的边都**小于 m i d mid mid**显然是一个解

因此我们不断使用二分即可找到答案

Mycode

const int N = 2e4+10 ;

struct node{
	int to,val;
};

vector g[N];
int n,m;
int  color[N];


bool dfs(int u,int c,int x){
	color[u] = c;
	for(auto j : g[u]){
		if(j.val n>>m;
	for(int i=1;i>a>>b>>c;
		g[a].pb({b,c});
		g[b].pb({a,c});
	}
	
	int l = 0 , r = 1e9;
	while(l>1;
		if(check(mid)) r = mid-1;
		else l = mid+1;
	}
	cout