USACO 2015 Gold January Contest Grass Cownoisseur: Longest Path on a DAG... With a Twist

Правка en1, от vamaddur, 2017-08-08 04:22:37

Problem: http://www.usaco.org/index.php?page=viewproblem2&cpid=516 Official Solution: http://www.usaco.org/current/data/sol_grass_gold.html

I was able to reduce the problem to solving it on a weighted DAG after compressing the graph into strongly connected components. However, I am not able to handle the caveat of being able to traverse a reversed edge at most once.

Is there a way to solve this final step of the problem without dynamic programming? If not, can someone explain what exactly is going on in the "solve" function and calls to it?

Please help, and thanks in advance!

Теги directed graph, dynamic programming

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский vamaddur 2017-08-08 04:22:37 681 Initial revision (published)