问题 26028 --最小比例

26028: 最小比例

时间限制: 1 Sec  内存限制: 128 MB
提交: 40  解决: 20
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][92kb]

题目描述

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

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

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

输入

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

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

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

输出

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

样例输入

3 2
30 20 10
0 6 2
6 0 3
2 3 0

样例输出

1 3

提示

对于30%数据,N<=5

来源

[提交][状态]