2937. 二分图的最大匹配
时间限制：1000 MS 内存限制：128 MB
题目描述
# 二分图的最大匹配 ## 题目描述 给定一个二分图，左部包含 $n_1$ 个顶点，编号为 $1$ 到 $n_1$；右部包含 $n_2$ 个顶点，编号为 $1$ 到 $n_2$。图中共有 $m$ 条边，每条边都连接一个左部顶点和一个右部顶点。 二分图的一个**匹配**是一个边的集合，其中任意两条边都没有公共端点。 在所有匹配中，包含边数最多的匹配称为**最大匹配**，其包含的边数称为**最大匹配数**。 请你求出给定二分图的最大匹配数。 ## 输入格式 从文件 `matching.in` 读入数据。 第一行包含三个整数 $n_1$、$n_2$ 和 $m$，分别表示左部顶点数、右部顶点数和边数。 接下来 $m$ 行，每行包含两个整数 $u$ 和 $v$，表示左部顶点 $u$ 与右部顶点 $v$ 之间有一条边。 ## 输出格式 将结果输出到文件 `matching.out`。 输出一个整数，表示给定二分图的最大匹配数。 ## 数据范围 - $1 \le n_1,n_2 \le 500$。 - $1 \le m \le 105$。 - $1 \le u \le n_1$。 - $1 \le v \le n_2$。 - 每条边均连接一个左部顶点和一个右部顶点。 ## 样例输入 ``` 2 2 4 1 1 1 2 2 1 2 2 ``` ## 样例输出 ``` 2 ``` ## 样例说明 选择连接左部顶点 $1$ 与右部顶点 $1$ 的边，以及连接左部顶点 $2$ 与右部顶点 $2$ 的边，即可得到一个包含 $2$ 条边的匹配。由于左部和右部各只有 $2$ 个顶点，最大匹配数为 $2$。 ## 时间与空间限制 - 时间限制：$1000$ 毫秒。 - 内存限制：$128$ MB。