编程介的小学生 2017-10-12 16:12 采纳率: 20.5%
浏览 1446
已采纳

Nikifor

Description

Nikifor has decided to present the dean of the Department of Mathematics and Mechanics with a linearly independent vector system (you know, that we've just celebrated jubilees of the University and of the Department). A store sells m items of n-dimensional vectors, m <= 2000, 3 <= n <= m. For each vector its price ci is known, 0 < i <= m. Nikifor wants to buy n linearly independent vectors paying for them minimal sum of money. Write a program that would determine which vectors Nikifor should buy or would inform that it is impossible to satisfy his requirements.
Input

The first line of an input contains numbers m and n separated with a space. The next m lines contain the vectors on sale. All of the coordinates are integers with an absolute value not exceeding 2 000. The numbers are separated from each other with a space. The next m lines contain prices ci, one number in each line. The prices are positive integers not exceeding 15 000.
Output

The first line of an output should contain the minimal amount of money that Nikifor is to pay or the number 0, if Nikifor's requirements cannot be satisfied in this store. If it is possible to make a purchase, then the next n lines should contain the numbers of the vectors that Nikifor should buy. If several sets of such numbers are possible, then you should write one of them which is minimal according to the lexicographic order.
Sample Input

5 3
1 0 0
0 1 0
0 0 1
0 0 2
0 0 3
10
20
30
10
10
Sample Output

40
1
2
4

  • 写回答

1条回答 默认 最新

  • threenewbee 2017-10-30 13:53
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 彩灯控制电路,会的加我QQ1482956179
  • ¥200 相机拍直接转存到电脑上 立拍立穿无线局域网传
  • ¥15 (关键词-电路设计)
  • ¥15 如何解决MIPS计算是否溢出
  • ¥15 vue中我代理了iframe,iframe却走的是路由,没有显示该显示的网站,这个该如何处理
  • ¥15 操作系统相关算法中while();的含义
  • ¥15 CNVcaller安装后无法找到文件
  • ¥15 visual studio2022中文乱码无法解决
  • ¥15 关于华为5g模块mh5000-31接线问题
  • ¥15 keil L6007U报错