| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3947 |
| 2 | jiangly | 3734 |
| 3 | Radewoosh | 3646 |
| 4 | jqdai0815 | 3620 |
| 4 | Benq | 3620 |
| 6 | orzdevinwang | 3612 |
| 7 | ecnerwala | 3581 |
| 8 | Geothermal | 3569 |
| 8 | cnnfls_csy | 3569 |
| 10 | ksun48 | 3479 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | awoo | 162 |
| 2 | maomao90 | 160 |
| 3 | nor | 156 |
| 4 | cry | 155 |
| 4 | adamant | 155 |
| 4 | atcoder_official | 155 |
| 4 | -is-this-fft- | 155 |
| 8 | maroonrk | 153 |
| 9 | SecondThread | 147 |
| 10 | Petr | 146 |
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
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.
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 .
probably the 1000th blog regarding TOURS problem
Hey Can you give me link of some blogs regarding TOURS problem