本文不对匈牙利算法的证明作解释。
预备知识
- 二分图： 设 (G=(V,E)) 是一个无向图，如果顶点 (V) 可分割为两个互不相交的子集 ((A,B)) ，并且图中的每条边 ((i，j)) 所关联的两个顶点 (i) 和 (j) 分别属于这两个不同的顶点集 ((i in A,j in B))，则称图 (G) 为一个二分图。
- 匹配：满足其中任意两条边都没有公共顶点的边集。
- 最大匹配：一个图所有匹配中，所含匹配边数最多的匹配，称为这个图的最大匹配。
简介
匈牙利算法用于求二分图的最大匹配。
模板题传送门：https://www.acwing.com/problem/content/description/863/
步骤
我们拿经典的男女配对来解释一下流程。
情境：给出 (n_1) 个男生， (n_2) 个女生，他们如果之间连边则代表着他们之间相互喜欢（不考虑同性恋（故保证是二分图））。
左边是男生，右边是女生。
一号男生和一、二号女生相互喜欢，二号男生和二、三号女生相互喜欢，三号男生和三号女生相互喜欢。
对于一号男生：
他和二号女生互相喜欢（假设他在找女友的时候优先遍历到二号女生），而二号女生现在没有男友，配对成功，返回。
对于二号男生：
他和三号女生互相喜欢（假设他在找女友的时候优先遍历到三号女生），而三号女生现在没有男友，配对成功，返回。
目前配对状况：
对于三号男生：
他和三号女生互相喜欢，但是此时三号女生有男友（二号）了，所以他标记了一下三号女生，然后去找到二号男生问他你能不能再去找一个其他女友（?），然后二号男生就去遍历他的女友，发现三号已经被标记了，但二号没有标记，但是此时二号女生有男友（一号）了，所以二号男生就标记了二号女生，类似于三号男生的行为，然后去找到一号男生问他你能不能再去找一个其他女友，一号男生也开始遍历自己的女友，最后发现一号女生没有标记，于是配对成功。
代码实现：
我们规定：
vis[i]=true 表示 i 号女生被标记，否则没有
match[i]=j 表示 i 号女生的男友是 j 号，如果没有男友则默认是 0
完整代码：
#include<bits/stdc++.h>
using namespace std;
const int N=505;
int n1,n2,m;
int h[N],tot;
struct node{
int to,next;
}e[N*N];
void add(int u,int v){e[tot].to=v, e[tot].next=h[u], h[u]=tot++;}
int match[N];
bool vis[N];
bool find(int x){
for(int i=h[x];~i;i=e[i].next){
int go=e[i].to;
if(!vis[go]){
vis[go]=true;
if(!match[go] || find(match[go])){
match[go]=x;
return true;
}
}
}
return false;
}
int main(){
memset(h,-1,sizeof h);
cin>>n1>>n2>>m;
while(m--){
int u,v; cin>>u>>v;
add(u,v);
}
int res=0;
for(int i=1;i<=n1;i++){
memset(vis,false,sizeof vis);
if(find(i)) res++;
}
cout<<res<<endl;
return 0;
}