#O1099. 二分图最大匹配
二分图最大匹配
题目描述
给定一个二分图:左部有 个点,右部有 个点,另有 条边。求这个二分图的最大匹配数。
输入格式
第一行三个整数 。
接下来 行,每行两个整数 ,表示左部点 与右部点 之间有一条边。
输出格式
一行一个整数,表示最大匹配数。
样例 #1
样例输入 #1
3 3 4
1 1
1 2
2 2
3 3
样例输出 #1
3
数据规模与约定
| 数据范围 | 说明 |
|---|---|
| 左右部点数 | |
| 边数,无重边 |
- 朴素匈牙利在稠密图上会退化,建议使用 Hopcroft-Karp。