Reach-Top OJ

问题 2615 --最小比例

2615: 最小比例

时间限制: 1 Sec 内存限制: 128 MB
提交: 8 解决: 5
[提交][状态][命题人:]

图中共有N个点的完全图，每条边都有权值，每个点也有权值。要求选出M个点和M-1条边，构成一棵树，使得：

即所有边的权值比所有点的权值之和的比率最小。

给定N和M，以及N个点的权值，和所有的边权，要求M个点的最小比率生成树。

第一行包含两个整数N和M(2<=N<=15，2<=M<=N)，表示点数和生成树的点数。

接下来一行N个整数，表示N个点的边权。

最后N行，每行N列，表示完全图中的边权。所有点权和边权都在[1,100]之间。

输出最小比率生成树的M个点。当答案出现多种时，要求输出的第一个点的编号尽量小，第一个相同，则第二个点的编号尽量小，依次类推，中间用空格分开。编号从1开始。

样例输入

Copy

样例输出

Copy

1 3

对于30%数据，N<=5。