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.


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.


Print a single integer that is the maximum number of pairs that can be obtained.


5 4 6
5 2
1 2
4 3
3 1
2 2
4 4


Cow 1 can be matched to bull 2, cow 3 to bull 1, and cow 4 to bull 3.

Note: see also

hide comments
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

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.
what should i do to make it accepted??
this is my sub mission=>,mahim007/

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)

Added by:Neal Wu
Time limit:0.400s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO