二分图

二分图是什么？可以吃吗

可以吃而且很好吃

当然不可以吃，但是使用起来可是个好东西

对于一张无向图，如果他的所有的点可以分成两个点集，且每个点集内的点没有边相连，我们就称这张图为二分图

对于判定二分图，我们有一种非常简单的方法 —— 染色法

染色法

染色？染什么色？

实际上如果有精通小学奥数的同学应该知道，我们在解决一类问题的时候，就会用到染色法来分类，当然，今天的原理，和那个染色法有一点类似

根据二分图的定义每个点集内的点没有边相连，我们可以知道，和一个点相连的两条边一定不在同一个集合中，那么如何判断是不是在同一集合呢？

我们就可以吧同一类的染上一个颜色，然后遍历图，如果我们在遍历某个点的时候，发现下一个点已经遍历过了，且和当前点颜色一样，那么这一定不是二分图

代码如下:

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);
}

请勿抄袭

END