← 返回题目

题库练习【模板】二分图最大匹配

← 上一题下一题 →

A2411 | $【模板】二分图最大匹配$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

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

输入格式

输入的第一行是三个整数，分别代表 $n$，$m$ 和 $e$。 接下来 $e$ 行，每行两个整数 $u, v$，表示存在一条连接左部点 $u$ 和右部点 $v$ 的边。

输出格式

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

输入输出样例

输入 #1

1 1 1
1 1

输出 #1

输入 #2

输出 #2

C++ 编辑器

输入

输出