ACM LIVE ARCHIVE 5882 — Racing Car Trail

Правка en1, от 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 :)!

Теги cerc 2011, question, live archive, maxflow, matching, 5882, racing car trail

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский ArepitaDePernil 2015-10-14 21:57:13 895 Initial revision (published)