AcWing 861：二分图的最大匹配 ← 匈牙利算法

【题目来源】
https://www.acwing.com/problem/content/863/

【题目描述】
给定一个二分图，其中左半部包含 n1 个点（编号 1∼n1），右半部包含 n2 个点（编号 1∼n2），二分图共包含 m 条边。
数据保证任意一条边的两个端点都不可能在同一部分中。
请你求出二分图的最大匹配数。

二分图的匹配：给定一个二分图 G，在 G 的一个子图 M 中，M 的边集 {E} 中的任意两条边都不依附于同一个顶点，则称 M 是一个匹配。
二分图的最大匹配：所有匹配中包含边数最多的一组匹配被称为二分图的最大匹配，其边数即为最大匹配数。

【输入格式】
第一行包含三个整数 n1、 n2 和 m。
接下来 m 行，每行包含两个整数 u 和 v，表示左半部点集中的点 u 和右半部点集中的点 v 之间存在一条边。

【输出格式】
输出一个整数，表示二分图的最大匹配数。

【数据范围】
1≤n1,n2≤500,
1≤u≤n1,
1≤v≤n2,
1≤m≤10^5

【输入样例】
2 2 4
1 1
1 2
2 1
2 2

【输出样例】
2

【算法分析】
●★ 理解匈牙利算法必知的概念

匹配：在图论中，一个「匹配」是一个边的集合，其中任意两条边都没有公共顶点。
最大匹配：一个图所有匹配中，所含匹配边数最多的匹配，称为这个图的最大匹配。
完美匹配：如果一个图的某个匹配中，所有的顶点都是匹配点，那么它就是一个完美匹配。
交替路：从一个未匹配点出发，依次经过非匹配边、匹配边、非匹配边…形成的路径叫交替路。
增广路：从一个未匹配点出发，走交替路，如果途径另一个未匹配点（出发的点不算），则这条交替路称为增广路（agumenting path）。

●★ “链式前向星”核心操作：https://blog.csdn.net/hnjzsyjyj/article/details/139369904
val[idx]：存储编号为 idx 的边的值
e[idx]：存储编号为 idx 的结点的值
ne[idx]：存储编号为 idx 的结点指向的结点的编号
h[a]：存储头结点 a 指向的结点的编号

【算法代码】

#include <bits/stdc++.h>
using namespace std;const int N=505;
const int M=1e5+5;
bool st[N];
int match[N];
int h[N],ne[M],e[M],idx;
int n1,n2,m;void add(int a,int b) {e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}int find(int u) {for(int i=h[u]; i!=-1; i=ne[i]) {int j=e[i];if(!st[j]) {st[j]=true;/*If girl j doesn't have a boyfriend, or her previous boyfriend can book other girls he likes.Pairing successful. */if(!match[j] || find(match[j])) {match[j]=u;return true;}}}return false;
}int main() {memset(h,-1,sizeof h);cin>>n1>>n2>>m;while(m--) {int a,b;cin>>a>>b;add(a,b);}int res=0;for(int i=1; i<=n1; i++) {memset(st,false,sizeof st);if(find(i)) res++;}cout<<res<<endl;return 0;
}/*
in:
2 2 4
1 1
1 2
2 1
2 2out:
2
*/

【参考文献】
https://www.acwing.com/solution/content/5334/
https://blog.csdn.net/hnjzsyjyj/article/details/139369904
https://www.acwing.com/solution/content/189267/