二分图最大匹配

时间：2024-01-28 13:32:03

概念：

二分图又称作二部图，是图论中的一种特殊模型。 设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。

是不是有些抽象？

整点直观的：

 

 如果一个图能转化成上面的这种亚子，那它就是一个二分图了。

那么，第一个问题就来了：

怎么判断一个图是不是二分图？

答案是：染色法。

观察一下：

二分图中父子节点所在的集合是不一样的，

不一样的集合便将点染成不同的颜色。

代码解释：

bool check(int mid){
    queue<int>q;
    memset(color,0,sizeof(color));//每一次check前要清零
    for(int i=1;i<=n;i++){
        if(color[i]) continue;//已经染过色的话就直接进行判断了
            q.push(i);color[i]=1;//用bfs防止爆栈
            while(!q.empty()){
                int x=q.front();q.pop();
                for(int j=head[x];j;j=eg[j].nex){
                    int y=eg[j].to;
                    if(!color[y]){
                        color[y]=3-color[x];//染成不同的颜色——1，2
                        q.push(y);
                    }
                    else if(color[y]==color[x]){//同色，矛盾，不是二分图
                        return false;
                    }
                }
            }
        }
    return true;
}

OK，接下来就是解决最大匹配的问题了。

这里有一篇文章讲的很不错，推荐一下：https://blog.csdn.net/JarjingX/article/details/8181073

大概思路是这样的：

把两个集合当做需要结婚的男人和女人，

给出他们的喜欢关系，

问最多能组成几对配偶。

如果这个男生喜欢的女生还没有结婚，

那就先让他们两个在一起，

如果结婚了，

那句找到她的现任男友，

看他能不能迁就一下，达成双赢。

代码详细解释：

bool find(int x){
    for(int i=head[x];i;i=edge[i].nex){
        int y=edge[i].to;
        if(!vis[y]){//如果还没有尝试去追求过
            vis[y]=1;//标记一下
            if(!match[y]||find(match[y])) {//如果目标还没有配偶或者他的配偶还可以将就,并且再返回时因为现在的配偶已经被标记，就不会陷入死循环啦~
            match[y]=x;//在一起（爱心）
            return true;//配对成功    
            }
        }
    }
    return false;//所有喜欢的人都不行，配对失败
}

这种没有节操，却又合乎情理的方法，就叫匈牙利算法。

 

相关文章