染色法判断二分图模板题 ----- 二分 + 染色法判断二分图
问题的转化
将罪犯当做点,罪犯之间的仇恨关系当做点与点之间的无向边,边的权重是罪犯之间的仇恨值。
那么原问题变成:将所有点分成两组,使得各组内边的权重的最大值尽可能小。
那么我们发现这个是一个经典的最大值最小问题,那么我们判断能否定义一个性质使得区间可以分成两段并具有二分性质
本题二分的性质
我们在 $[0,10^{9}]$ 之间枚举最大边权 $limit$,当 $limit$ 固定之后,剩下的问题就是:
判断能否将所有点分成两组,使得所有权值大于 $limit$ 的边都在组间,而不在组内。也就是判断由所有点以及所有权值大于 $limit$ 的边构成的新图是否是二分图。
判断二分图可以用染色法,时间复杂度是 $O(N+M)$,其中 $N$ 是点数,$M$ 是边数,可以参考 AcWing 860. 染色法判定二分图
判断是否具有两段性
假定最终最大边权的最小值是 $Ans$:
-
那么当 $imit∈[ans,10^{9}] $时,所有边权大于 $limit$的边,必然是所有边权大于$ans$的边的子集,因此由此构成的新图也是二分图。
-
当 $limit∈[0,ans−1]$时,由于 $ans$是新图可以构成二分图的最小值,因此由小于等于 $limit$ 的边构成的新图一定不是二分图。
-
所以整个区间具有二段性,可以二分出分界点 ans 的值。
c++代码
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 20010,M = 200010;
int h[N],ne[M],e[M],w[M],idx;
int color[N]; //color[i]表示i节点被染上的颜色(属于什么集合)
int n,m;
void add(int a,int b,int c){
w[idx] = c;
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
//用染色法判断所有大于mid的节点是否是二分图
bool dfs(int u,int c,int mid){
color[u] = c;
for(int i = h[u];i != -1;i = ne[i]){
int j = e[i];
if(w[i] <= mid) continue;
if(!color[j]){
//一票否决,直接链式反应一路返回false
if(!dfs(j,3 - c,mid)) return false; //否则将u节点染成3 - c色
}else if(color[j] == c) return false;
}
return true;
}
//因为不一定只有一个连通块,所以是否所有连通块都可以染色成功
bool check(int mid){ //判断是否可以将大于mid的节点分成两个集合
memset(color,0,sizeof color);
for(int i = 1;i <= n;++i){
if(color[i] == 0){
if(!dfs(i,1,mid)) return false;
}
}
return true;
}
int main(){
memset(h,-1,sizeof h);
scanf("%d%d",&n,&m);
for(int i = 0;i < m;++i){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a,b,c); add(b,a,c);
}
int l = 0, r = 1e9;
//二分:将所有大于mid的节点能否分成一张二分图
while(l < r){ //整张图是二分图的时候不需要特判,因为二分可以求出0这个结果
int mid = (l + r) >> 1;
if(check(mid)) r = mid;
else l = mid + 1;
}
cout << r << endl;
return 0;
}