ArepitaDePernil's blog

By ArepitaDePernil, history, 9 years ago, In English

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 :)!