定义
二分图:
二分图又称作二部图,是图论中的一种特殊模型。 设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;
}