Problem3008--K个最小和[K Smallest Sums,UVa11997]

3008: K个最小和[K Smallest Sums,UVa11997]

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 0  Solved: 0
[Status] [Submit] [Creator:]

Description

有K个数组，每个数组都包含K个整数，从每个数组中取一个元素加起来，一共有K^K种选择方式，从而可以得到K^K个和，求这些和中最小的k个值（重复的值算多次）

Input

输入包含多组测试数据。
每组数据：
第一行，一个整数K（2≤K≤750）
接下来K行，每行K个整数，整数之间用空格隔开，且整数的范围都不超过10^6.输入文件的大小不超过5M

Output

对于每组数据，输出一行，输出K个最小和的值，并按照从小到大的顺序排序

Sample Input Copy 

3 
1 8 5 
9 2 5 
10 7 6 
2
1 1 
1 2

Sample Output Copy 

9 10 12 
2 2

Source/Category

优先队列 UVA level6 
[Submit] [Status]