二分图最大匹配

时间: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;//所有喜欢的人都不行,配对失败
}

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