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
lukaszpolska:
2023-10-14 23:01:39
Can somone explain why Edmond karp with 2 additional vertices dont work here (wa on test 7)? |
|
treenipples:
2021-05-23 12:34:10
Kuhn's BPM passes if you shuffle the graph Last edit: 2021-05-23 20:02:16 |
|
nemesys:
2020-10-09 04:59:49
Got TLE with Dinic |
|
emej:
2020-03-15 17:24:01
Edmond karp barely passes |
|
threat_:
2019-10-16 02:42:51
Edmond Karp passes |
|
msh2481:
2018-10-02 07:04:04
Fast Kuhn get AC) |
|
joqsan_77:
2018-08-22 16:54:52
A well-written Dinic's algorithm passes. |
|
vincecao:
2017-12-05 12:50:13
always tle made me try every possible way to reduce the time cost, however it resulted in the bug in HK causing the dead loop... |
|
simp:
2017-11-21 04:06:56
Kuhn will not pass, you should use algorithm Hopcroft-Karp. |
|
br4in1:
2017-11-20 16:12:24
simple dp |
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 |