二、AcWing 861. 二分图的最大匹配
本题链接：AcWing 861. 二分图的最大匹配
本博客给出本题截图：
本题分析
注意本题是无向图，但是根据我们上述的对匈牙利算法实现的讲解中可以看出来，其实我们只需要当成有向图去做就好了，即当成男追女，而不是双向奔赴.
match数组代表的含义就是找对象，match[i] = j;的意思就是女朋友i的男朋友为j，match[j] == 0意味着没有男朋友
st数组的含义是是否被选定了，st[i] == false意味着i这个女嘉宾没有被其他男嘉宾选定
if (match[j] == 0 || find(match[j])) { match[j] = x; return true; }
这里的意思是如果j号女嘉宾没有男嘉宾，或者j号女嘉宾现在的对象有备胎，那么就让j号女嘉宾成为x号男嘉宾的对象
for (int i = 1; i <= n1; i ++ ) { memset(st, false, sizeof st); if (find(i)) res ++ ; }
每一个男嘉宾开始寻找女嘉宾的时候，都是默认女嘉宾没有对象的，因为有对象就抢
AC代码
#include <cstring> #include <cstdio> #include <algorithm> using namespace std; const int N = 510, M = 100010; int n1, n2, m; int h[N], e[M], ne[M], idx; int match[N]; bool st[N]; void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ; } bool find(int x) { for (int i = h[x]; i != -1; i = ne[i]) { int j = e[i]; if (!st[j]) { st[j] = true; if (match[j] == 0 || find(match[j])) { match[j] = x; return true; } } } return false; } int main() { scanf("%d%d%d", &n1, &n2, &m); memset(h, -1, sizeof h); while (m -- ) { int a, b; scanf("%d%d", &a, &b); add(a, b); } int res = 0; for (int i = 1; i <= n1; i ++ ) { memset(st, false, sizeof st); if (find(i)) res ++ ; } printf("%d\n", res); return 0; }
三、时间复杂度
关于匈牙利算法的时间复杂度以及证明，后续会给出详细的说明以及证明过程，目前先鸽了。
