txhai12's blog

By txhai12, history, 2 years ago, In English

Hi, I'm just done like 40 submission of this problem (https://www.spoj.com/problems/GOODA/). I really stuck thinking why my solution get ac, pls help me. Give a directed graph, an array of value of each city, s — start city, e — end city and ask for choosing a path from s to e and the path have maximum value of city on the path. Guarantee that e is reachable from s.

I converting the directed graph to condensation graph (DAG) (by this technique https://cp-algorithms.com/graph/strongly-connected-components.html) and do dp. But i think in the first dfs(dfs1) I just need to dfs1 start from the s, in stead of staring from every node u that used[u] = false, bcuz e is reachable from s.

void dfs1(int u){
   used[u] = true;
   for(auto v : adj[u]){
      if(!used[v]){
         dfs1(v)
      }  
   }

   st.epb(u);
}


// the normal and get ac

for(int i = 1 ; i <= n ; i++){
   if (!used[i]){
      dfs1(i);
   }
}
// ====

// i think problem just need to, but i get WA
dfs1(s);
// =====

Here is my code get ac, https://ideone.com/6KwRpb

Can u guys give me some test case that my think will wrong. Thanks for reading, sorry for my bad English :((

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

| Write comment?
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You need to find strongly connected components and then condense the graph and then use dp on the condensed graph as per the topological ordering of the graph.

I believe this blog contains all the relevant details

https://cp-algorithms.com/graph/strongly-connected-components.html

Good luck :)

AC Code: