欢迎加入西电微软俱乐部招新群 588166170,做出福利题,免技术部第一次面试且赠送“福利”海报或小礼品~~~~

问题 1048. -- 二分匹配模板测试

1048: 二分匹配模板测试

时间限制: 1 Sec  内存限制: 128 MB
提交: 85  解决: 30
[提交][状态][讨论版]

题目描述

西电ACM实验室是一个很和谐的实验室,有n个男生和m个女生组成(m>0),尽管表面大家都全心全意地为了荣誉而战,然而经过亮亮的深入调查,我们已经知道了有一些人三心二意:每天只有99%的时间花费在切题上,而还有1%的时间在想着某位或某几位异性!作为FFF团西电分部的部长,亮亮显然不能容许这种朝三暮四的情况。但是西电ACM实验室又是一个很开明的实验室,于是亮亮决定尽可能的撮合实验室的队员!

那么问题来了,亮亮最多能撮合多少对呢?

输入

多组数据,每组数据首先是两个整数,n,m表示男女生的人数(0<n,m<=500).

接下来是一个整数l(0<=l<=200000)表示亮亮搜集得到的关系

接下来是l行,每行是两个数u,v(0<=u<n,0<=v<m)

表示第u位男生和第v位女生有情况!

由于ACM实验室是个和谐的大家庭,因此不会出现同性恋。

输出

对于每组数据,输出一个整数,表示亮亮能撮合的对数。

样例输入

2 2
2
1 1
2 1

样例输出

1

提示

故事是这样的,ACM实验室有两个男生,一个是高富帅,一个是穷屌丝,同时又有两个女生,一个是白富美,一个是女汉子,然而两个男生都喜欢白富美,最终白富美选择了高富帅,过上了幸福快乐的生活,穷屌丝和女汉子注孤生。


所以输出1(因为只有一对被亮亮撮合了)


来源

[提交][状态][讨论版]