Description given a weighted graph G, each edge has a non-negative integer weights. The objective is to find G, one through each vertex once and only after the last loop, the minimum value of the total weight of the loop. Please design a 2- approximation algorithm to find the approximate minimum total weight, that is to define the optimal solution C, as long as the output solution [C, 2* C] range of the " Accept" . Input The first acts of a positive integer n (1 < = n < = 20), the number of said G vertices. The next n lines each line contains n integers, the i-th row j th integer weights in G i-th point to the j th point. Input to ensure that G [i, j] = G [j, i], and G [i, i] = 0 Output Output an integer loop approximate minimum weight value C*. The second line is composed of n vertices and serial number (from 0 label) corresponding to the approximate solution of the Hamiltonian circuit.

acm1106.cpp

• We are an exchange download platform that only provides communication channels. The downloaded content comes from the internet. Except for download issues, please Google on your own.
• The downloaded content is provided for members to upload. If it unintentionally infringes on your copyright, please contact us.
• Please use Winrar for decompression tools
• If download fail, Try it againg or Feedback to us.
• If downloaded content did not match the introduction, Feedback to us，Confirm and will be refund.
• Before downloading, you can inquire through the uploaded person information

Nothing．