A.K.Goharshady's blog

By A.K.Goharshady, 8 years ago, In English,
This one has two different linear-time solutions. Greedy and dynamic programming.

Greedy solution:
You should stop at the city with maximum distance from the root (city number 1). So all roads are traversed twice except for the roads between the root and this city.

Dynamic Programming:
For each city i we declare patrol[i] as the traverse needed for seeing i and all of it's children without having to come back to i (Children of a city are those cities adjacent to it which are farther from the root) and revpatrol[i] as the traverse needed to see all children of i and coming back to it. we can see that revpatrol[i] is sum of revpatrols of its children + sum of lengths of roads going from i to its children. patrol[i] can be found by replacing each of revpatrols with patrol and choosing their minimum.

  • Vote: I like it  
  • +7
  • Vote: I do not like it  

22 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

please explain a bit about the dynamic programming approach for this problem...how can you traverse all the childs of i without traversing it again... suppose i has 2 branches then after travelling the first branch in graph, we must return to i to move to second branch.. thus how is patrol[i] is defined in those cases where the parent has more than 1 child.

14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

It is not clear that how patrol[i] be calculated...Please explain in detail....