MATCHING - Fast Maximum Matching
FJ has N (1 ≤ N ≤ 50,000) cows and M (1 ≤ M ≤ 50,000) bulls. Given a list of P (1 ≤ P ≤ 150,000) potential matches between a cow and a bull, compute the greatest number of pairs that can be matched. Of course, a cow can be matched to at most one bull, and vice versa.
Input
The first line contains three integers, N, M, and P. Each of the next P lines contains two integers A (1 ≤ A ≤ N) and B (1 ≤ B ≤ M), denoting that cow A can be matched with bull B.
Output
Print a single integer that is the maximum number of pairs that can be obtained.
Example
Input: 5 4 6 5 2 1 2 4 3 3 1 2 2 4 4 Output: 3
Cow 1 can be matched to bull 2, cow 3 to bull 1, and cow 4 to bull 3.
Note: see also http://www.spoj.com/problems/FASTFLOW/.
hide comments
Luis Manuel Díaz Barón:
2017-05-29 17:34:09
Kuhn -> TLE .... WHY???? Has anyone got AC using Kuhn ?? |
|
hamzaziadeh:
2016-10-16 21:07:37
ac in 1 go, easy problem for beginners. |
|
Jeenu Grover:
2016-07-18 09:20:07
@ufrnmaratona Did you find out why are you getting a wrong answer. I have done the same thing and wrong answer. I f possible please give a test case. |
|
Ashraful Islam:
2016-02-16 22:05:56
please some one help me,i use kuhn's algorithm and get TLE.
|
|
dacin21:
2016-02-13 15:43:34
Wait, why does lowest label push relabel pass while highest label is to slow?? (Using a pretty optimized implementation) |
|
andre schurrle:
2015-06-06 13:43:58
Last edit: 2015-06-15 05:17:33 |
|
(Tjandra Satria Gunawan)(曾毅昆):
2015-05-29 00:45:06
From TLE to top 10 fastest -_-
|
|
Rishab Kalra:
2014-01-17 16:50:02
getting wrong answer at 7th test case...any special case?
|
|
abdelkarim:
2013-07-07 06:34:32
@changiz
|
|
ByambadorjP:
2012-07-23 06:35:13
Hi guys. I solved this problem in runtime nearly 3. But many people solved this problem better than my runtime. Please send me a better solution to my email. byambadorjp@gmail.com please!!! |
Added by: | Neal Wu |
Date: | 2009-04-12 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO |