Problem 26028 --最小比例

26028: 最小比例

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 40  Solved: 20
[Submit][Status][Web Board][Creator:][下载FPS1元][添加到购物车][下载测试数据1元][92kb]

Description

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

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

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

Input

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

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

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

Output

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

Sample Input

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

Sample Output

1 3

HINT

对于30%数据,N<=5

Source

[Submit][Status]