Description: 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.
To Search:
File list (Check if you may need any files):
acm1106.cpp
Download