Descr iption

　　给定一个完全无向带权图G，其每一条边有一个非负的整数权值。目的是要找出G的一条经过每个顶点一次且仅经过一次的回路，使回路的总权值最小。

　　请设计一个2-近似算法，求出近似最小的总权值，即定义最优解为C，只要输出解在[C , 2 * C]的范围内都可以“Accept”。







Input

　　输入第一行为一个正整数n(1 <= n <= 20)，表示G中顶点的个数。接下来n行每行包括n个整数，第i行第j个的整数表示G中第i个点到第j个点的权值。

　　输入保证G[i,j] = G[j,i],且G[i,i] = 0.







Output

　　输出一个整数表示回路的近似最小权值C*。

　　第二行为n个顶点序号（从0开始标号）组成的与近似解相应的哈密顿回路。-Descr iption 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.