Блог пользователя raj_meena

WA on SPOJ TOURS
Автор raj_meena, история, 9 лет назад, По-английски

http://www.spoj.com/problems/TOURS/ Above is problem link. My approach is follow :

1. Find All Pairs Shortest paths
2. Create Flow Network where flow will be 1 and cost will be distance from i to j.
3. Add Super Source and Super Sink then Using mincostmaxflow find minimum cost print it.

Any Hint?? , Test case, your approach anything all are welcome :D :)

Sorry for my poor english

  • Проголосовать: нравится
  • -4
  • Проголосовать: не нравится

»
9 лет назад, # |
← Rev. 5   Проголосовать: нравится +1 Проголосовать: не нравится

What kind of flow network are you creating?

If you build a bipartite graph and perform min-cost max-flow, it will give you the minimum cost to match nodes. Additionally, each node will have in-degree 1 and out-degree 1, so it will be cyclical.

A regular graph won't work.

Also, you just have to add edges as given in the input. There's no need to find all pairs shortest paths. In fact, if you add edges based on shortest paths, it will surely give you WA, because some places will be visited more than once.

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Hey yes i was creating bipartite graph and also flow will be 1 for each vertex from super source and also in super sink. and thank you so much tenshi_kanade i got AC just remove flyod warshall from code. :D :) i didn't notice that using shortest path vertexes can be occur multiple times :D .

    → Ответить
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

probably the 1000th blog regarding TOURS problem

→ Ответить