二分图
二分图是什么?可以吃吗
染色法
染色?染什么色?实际上如果有精通小学奥数的同学应该知道,我们在解决一类问题的时候,就会用到染色法来分类,当然,今天的原理,和那个染色法有一点类似 根据二分图的定义
每个点集内的点没有边相连
,我们可以知道,和一个点相连的两条边一定不在同一个集合中,那么如何判断是不是在同一集合呢?
我们就可以吧同一类的染上一个颜色,然后遍历图,如果我们在遍历某个点的时候,发现下一个点已经遍历过了,且和当前点颜色一样,那么这一定不是二分图
代码如下:
inline bool bfs(int u){// u 起始点
head=tail=0;// 队列初始化
col[u]=1;// 初始化起点
q[head]=u;// 加入对头
while(head<=tail){// 标准不解释
int top=q[head];// 去头部
for(int i=ehead[top];i;i=e[i].next){// 标准遍历不解释
int to=e[i].to;
if(col[to]==0){// 如果没有被访问过
col[to]=3-col[top];// 染色
q[++tail]=to;// 加入队列
}
else {// 访问过
if(col[to]==col[top]) return false;// 颜色相同当然不是二分图了
}
}
head++;
}
return true;
}
但是有的时候,输入数据不保证为一张图,这个时候就要遍历点,如果当前点没有访问过,那么就从当前点起始染色
Luopu P1525 关押罪犯
二分查找二分图 题目链接: [https://www.luogu.org/problemnew/show/P1525]第一眼看过去,这是什么?可和二分图有啥关系 然后看了看书,突然就明白了 我们可以二分事件的最大影响值,把每个罪犯看做一个点,如果影响值大于
mid
那么就链接,否则当不存在这条边
所以这道题目就是一个二分模板+染色判二分图
程序
#include <cstdio>
#include <cstring>
using namespace std;
int n,m;
int u,w,v;
int l,r,mid,max;
// edge start
struct edge{
int to,next,val;
}e[210000];
int ehead[21000],ecnt;
inline void add(int now,int to,int val){
ecnt++;
e[ecnt].to=to;
e[ecnt].val=val;
e[ecnt].next=ehead[now];
ehead[now]=ecnt;
}
// edge end
// edge 链表建图部分
// queue start
int q[110000],head,tail;
int col[110000];
inline bool bfs(int u){
head=tail=0;
col[u]=1;
q[head]=u;
while(head<=tail){
int top=q[head];
for(int i=ehead[top];i;i=e[i].next){
int to=e[i].to;
if(e[i].val>=mid){// 大于等于mid时建边
if(col[to]==0){
col[to]=3-col[top];
q[++tail]=to;
}
else {
if(col[to]==col[top]) return false;
}
}
}
head++;
}
return true;
}
// queue end
// queue 染色法判图
inline bool rs(){
for(int i=1;i<=n;i++){
if(col[i]==0)
if(!bfs(i)) return false;
}
return true;
}
// rs 遍历点
inline void init(){
memset(col,0,sizeof(col));
}
// init 预处理
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d%d%d",&u,&v,&w);
max=max>w?max:w;// 保留最大用于二分上限
add(u,v,w);
add(v,u,w);
}
l=0,r=max+1;// 标准二分
while(l+1<r){
init();
mid=(l+r)>>1;
if(rs()) r=mid;// 如果可以达成[二分图成立] 则缩小范围
else l=mid;// 不可以就扩大范围
}
printf("%d",l);
}
请勿抄袭