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.

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.

good

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.