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

Автор ArepitaDePernil, история, 9 лет назад, По-английски

Hello, i am strugling to understand how this problem is solved, in the outlines from CERC 2011 , it states that we need to find maximum matching, and then calculate the maximum matching without starting node, and then find an augmenting path.

I have an idea of why they use this tactic to tackle the problem, however i don't understand how you find an augmenting path without an especific sink, also i would like some clarification since this outline is pretty confusing, especially when they say: "starting in an unmatched node = lose" , but then they state that you need the augmenting path. Can anybody explain this solution to me? i am pretty ok with networkflows, so i think i can understand it if somebody explains it to me, i am aware this problem is like top hard problem in that contest, however i am pretty interested in it. Thanks a lot :)!

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