Editorial for APIO '09 P3 - The Great ATM Robbery
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Decompose the graph into its Strongly connected components (SCCs). Clearly, if Banditji visits any such component, he will rob every node in the component. The set of SCCs forms a DAG and we would like the find the longest path in this resulting DAG (where every node has weight equal to the sum of the reserves at all ATMs in the component) from the component with the city center to any component containing a pub. This algorithm should run in time linear in the number of edges.
Comments