A29716.二分图最大匹配

入门

官方

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

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

输入格式

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

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

输出格式

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

输入输出样例

  • 输入#1

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

    输出#1

    2

说明/提示

数据规模与约定
对于全部的测试点,保证:
1≤n,m≤500。
1≤e≤5*10^4
1≤u≤n , 1≤v≤m。
不保证给出的图没有重边。 https://ks.wjx.top/vm/mBA6Tkl.aspx

首页