game_changer007's blog

bipartite matching
By game_changer007, 11 years ago, In English

Hi, I tried to understand bipartite matching from here But it was different from the normal max-flow code.(Dinics for example).What is its proof of corectness and its complexity?

Thanx

  • Vote: I like it
  • +17
  • Vote: I do not like it

»
11 years ago, hide # |
← Rev. 5  
Vote: I like it +9 Vote: I do not like it

Hi! I have learnt maximum bipartite matching from those two videos:

First

Second

It's explained very well, I think its complexity is O(N^3).

For practice: http://lightoj.com/volume_showproblem.php?problem=1184 //You need a registration to see the problem.

My accepted code(it might be helpful to understand it better): http://ideone.com/lGgTXz

→ Reply
  • »
    »
    11 years ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it +1 Vote: I do not like it

    Thank you , that was really helpful . If you know about any nice resource for learning Hopcroft-Karp please can you share that too ?

    → Reply
    • »
      »
      »
      11 years ago, hide # ^ |
      ← Rev. 2  
      Vote: I like it +3 Vote: I do not like it

      Unfortunately, I don't know anything about Hopcroft-Karp matching. Maybe I will try to learn it this week if I find a good tutorial on it. By the way, can anyone with more experience describe it or recommend an article/video, please? :)

      → Reply