Блог пользователя game_changer007

bipartite matching
Автор game_changer007, 11 лет назад, По-английски

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

  • Проголосовать: нравится
  • +17
  • Проголосовать: не нравится

»
11 лет назад, скрыть # |
← Rev. 5  
Проголосовать: нравится +9 Проголосовать: не нравится

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

→ Ответить