ACM LIVE ARCHIVE 5882 — Racing Car Trail

Revision en1, by ArepitaDePernil, 2015-10-14 21:57:13

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

Tags cerc 2011, question, live archive, maxflow, matching, 5882, racing car trail

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English ArepitaDePernil 2015-10-14 21:57:13 895 Initial revision (published)