【模板】二分图最大匹配(Bipartite Matching)

题目描述

给定一个二分图，其左部点的个数为 $n$，右部点的个数为 $m$，边数为 $e$，求其最大匹配的边数。

左部点从 $1$ 至 $n$ 编号，右部点从 $1$ 至 $m$ 编号。

输入格式

输入的第一行是三个整数，分别代表 $n$，$m$ 和 $e$。

接下来 $e$ 行，每行两个整数 $u, v$，表示存在一条连接左部点 $u$ 和右部点 $v$ 的边。

输出格式

输出一行一个整数，代表二分图最大匹配的边数。

样例输入 #1

1 1 1
1 1

样例输出 #1

1

样例输入 #2

4 2 7
3 1
1 2
3 2
1 1
4 2
4 1
1 1

样例输出 #2

2

数据范围

数据规模与约定

对于全部的测试点，保证：

• $1 \leq n, m \leq 500$。
• $1 \leq e \leq 5 \times 10^4$。
• $1 \leq u \leq n$，$1 \leq v \leq m$。

不保证给出的图没有重边。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1400。

测试点分布

出处：原题链接