HDU 2489 Minimal Ratio Tree （DFS枚举+最小生成树Prim）

HDU 2489 Minimal Ratio Tree （DFS枚举+最小生成树Prim）2014-10-25 csdn博客 shuangde800链接：

HDU ： http://acm.hdu.edu.cn/showproblem.php？pid=2489

POJ ： http://poj.org/problem？id=3925

题目：

Problem Description

For a tree, which nodes and edges are all weighted, the ratio of it is calculated according to the following equation.

Given a complete graph of n nodes with all nodes and edges weighted, your task is to find a tree, which is a sub-graph of the original graph, with m nodes and whose ratio is the smallest among all the trees of m nodes in the graph.

Input

Input contains multiple test cases. The first line of each test case contains two integers n （2<=n<=15） and m （2<=m<=n）, which stands for the number of nodes in the graph and the number of nodes in the minimal ratio tree. Two zeros end the input. The next line contains n numbers which stand for the weight of each node. The following n lines contain a diagonally symmetrical n×n connectivity matrix with each element shows the weight of the edge connecting one node with another. Of course, the diagonal will be all 0, since there is no edge connecting a node with itself.

All the weights of both nodes and edges （except for the ones on the diagonal of the matrix） are integers and in the range of [1, 100].

The figure below illustrates the first test case in sample input. Node 1 and Node 3 form the minimal ratio tree.

Output

For each test case output one line contains a sequence of the m nodes which constructs the minimal ratio tree. Nodes should be arranged in ascending order. If there are several such sequences, pick the one which has the smallest node number; if there"s a tie, look at the second smallest node number, etc. Please note that the nodes are numbered from 1 .

Sample Input

3 230 20 100 6 26 0 32 3 02 21 10 22 00 0

Sample Output

1 31 2

题目大意：

有一个n个点的图，然后给出n*n的邻接矩阵图，要求这个图的m个结点的子图，使得这个子图所有边之和与所有点之和的商值最小。