|
|
back to boardShow all messages Hide all messages830701 17:26:25
22 Apr 2005 Fu Dong 1063 Pascal Accepted
0.015 149 KB
First, I connected all the blocks , then I used DFS to make a Eular_Graph and find the minimal cost.
I know this problem is a famous problem, maybe it is called "China post road problem", who can tell me the best solution to this problem.
I'm sorry, my English is so poor. I think we could get a better answer through greed,the algorithm will be very fast then. But ... I got wa , I didn't know why. It is not called "China post road problem". In that problem road can't be add, you can use Eular Road to solve that problem, and I think you can also use it in this problem. 830701 17:26:25
22 Apr 2005 Fu Dong 1063 Pascal Accepted
0.015 149 KB
First, I connected all the blocks , then I used DFS to make a Eular_Graph and find the minimal cost.
I know this problem is a famous problem, maybe it is called "China post road problem", who can tell me the best solution to this problem.
I'm sorry, my English is so poor. In China post road problem net is given but here
we are to build best euler net. I think that correct solution uses some sort of full search and belong to NP-problems. Thus main question- Are the problen of NP type. ASK FOR SOLUTION:
cpp_student@163.com
THX!:) Once you connect all components, you don't need to find an Euler cycle, just pick all odd-degree nodes sequentially, except for the last two (sorted ascendingly).
Anyway, the search for cheapest connection plan is recursive. |
|
|
