二分图最大匹配

定义

二分图:

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

简单的说,一个图被分成了两部分,相同的部分没有边,那这个图就是二分图,二分图是特殊的图。

匹配:

给定一个二分图G,在G的一个子图M中,M的边集{E}中的任意两条边都不依附于同一个顶点,则称M是一个匹配。
极大匹配(Maximal Matching)是指在当前已完成的匹配下,无法再通过增加未完成匹配的边的方式来增加匹配的边数。

最大匹配(maximum matching)是所有极大匹配当中边数最大的一个匹配。选择这样的边数最大的子集称为图的最大匹配问题。
如果一个匹配中,图中的每个顶点都和图中某条边相关联,则称此匹配为完全匹配,也称作完备匹配。
二分图匹配可以用最大流(Maximal Flow)或者匈牙利算法(Hungarian Algorithm)(用途极其广泛)

匈牙利算法

匈牙利算法几乎是二分图匹配的核心算法,除了二分图多重匹配外均可使用

匈牙利算法实际上就是一种网络流的思想,其核心就是寻找增广路。具体操作可以理解为女选男,男抢女。(男尽量有女)

那么来描述一下算法流程:

假设你有n个剩男和m个剩女,其中每个男有几个中意的女子,我们要做的就是尽量让他们成功,让情侣对数最多。(典型的单身狗自虐环节)那么我们究竟该怎么办呢?

首先:表格中,1表示相互可以匹配,0表示:你我本无缘。

b1 b2 b3 b4
g2 1 1 1 0
g1 1 0 1 0
g3 0 1 0 1
g4 0 0 0 0

1.先试着给1号男生找妹子,发现第一个和他相连的1号女生有机会,匹配

b1 b2 b3 b4
匹配人 g1

2.然后接着给2号男生找妹子,发现第一个和他相连的2号女生有机会,匹配

b1 b2 b3 b4
匹配人 g1 g2

3.接下来是3号男生,很遗憾1号女生已经有主了,怎么办呢?

4.我们试着给之前1号女生匹配的男生(也就是1号男生)另外分配一个妹子,将原来的标记删除(暂时)

b1 b2 b3 b4
匹配人 (暂时空) g2
原配 g1

5.与1号男生相连的第二个女生是2号女生,但是2号女生也有主了,怎么办呢?我们再试着给2号男生重新找个妹子(注意这个步骤和上面是一样的,是一个递归的过程)

b1 b2 b3 b4
匹配人 (暂时空) (暂时空)
原配 g1 g2

6.此时发现2号男生还能找到3号女生,那么之前的问题迎刃而解了,回溯回去

b1 b2 b3 b4
匹配人 g2 g3 g1

end: 于是:2号男生可以找3号妹子 1号男生可以找2号妹子了 3号男生可以找1号妹子,可惜的是:重复以上步骤,4号男生单身了(或许是他太帅了。。。。),4号女生也单身了(或许她是个如花的姑娘。。。。)。(这两个老寡王了。。。。)

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int N=505;
int line[N][N];
int girl[N],used[N];
int k,m,n;
bool found(int x){
    for(int i=1; i<=n; i++){
        if(line[x][i]&&!used[i]){
            used[i]=1;
            if(girl[i]==0||found(girl[i])){
                girl[i]=x;
                return 1;
            }
        }
    }
    return 0;
}

int main(){
    int x,y;
    while(scanf("%d",&k)&&k){
        scanf("%d %d",&m,&n);
        memset(line,0,sizeof(line));
        memset(girl,0,sizeof(girl));
        for(int i=0; i<k; i++){
            scanf("%d %d",&x,&y);
            line[x][y]=1;
        }
        int sum=0;
        for(int i=1; i<=m; i++){
            memset(used,0,sizeof(used));
            if(found(i)) sum++;
        }
        printf("%d\n",sum);
    }
    return 0;
}
上一篇:Java 12 新特性概述


下一篇:jvm gc知识