#O1099. 二分图最大匹配

二分图最大匹配

题目描述

给定一个二分图:左部有 nn 个点,右部有 mm 个点,另有 ee 条边。求这个二分图的最大匹配数。

输入格式

第一行三个整数 n,m,en,m,e。

接下来 ee 行,每行两个整数 u,vu,v,表示左部点 uu 与右部点 vv 之间有一条边。

输出格式

一行一个整数,表示最大匹配数。

样例 #1

样例输入 #1

3 3 4
1 1
1 2
2 2
3 3

样例输出 #1

3

数据规模与约定

数据范围 说明
1≤n,m≤20001 \le n,m \le 2000 左右部点数
1≤e≤1051 \le e \le 10^5 边数,无重边
  • 朴素匈牙利在稠密图上会退化,建议使用 Hopcroft-Karp。