You’re given k arrays, each array has k integers. There are k
k ways to pick exactly one element in each
array and calculate the sum of the integers. Your task is to find the k smallest sums among them.
Input
There will be several test cases. The first line of each case contains an integer k (2 ≤ k ≤ 750). Each of
the following k lines contains k positive integers in each array. Each of these integers does not exceed
1,000,000. The input is terminated by end-of-file (EOF).
Output
For each test case, print the k smallest sums, in ascending order.
Sample Input
3
1 8 5
9 2 5
10 7 6
2
1 1
1 2
Sample Output
9 10 12
2 2

题目大意：
给定n组数组，每组数组有n个元素，每个数组取一个元素一共有n的n次方种组合，问哪种组合使得他们的和最小，输出n种组合的最小和（递增输出）。
思路：先将每组数据排序，然后再归并求最小和。
因为每个数组第一个元素都是最小值，所以组合起来也是最小值，然后归并起来，再用这个思路去做就可以了。这里用到了优先队列的自动排序。

代码：

#include<iostream>
#include<queue>
#include<bits/stdc++.h>
#include<algorithm>
#define MAXN 750
using namespace std;

int a[MAXN][MAXN]; 

struct node
{
	int sum;//这个用的秒 
	int coordinate;
	node(int sum,int coordinate):sum(sum),coordinate(coordinate){
	}
	bool operator<(const node &a)const{
		return sum>a.sum;
	}
};
void merge(int *a,int *b,int *c,int n)
{
	priority_queue<node>pp;
	for(int i=0;i<n;i++){//因为数组a和b都已经排序过了，所以可以保证
	//push的第一一个元素一定是当前最小值，0代表b数组元素的下标，都是从0开始 
		pp.push(node(a[i]+b[0],0));
	}
	for(int i=0;i<n;i++){//优先队列的top都是最小值 
		node q=pp.top();
		pp.pop();
		c[i]=q.sum;
		int bb=q.coordinate;
		if(bb+1<n){//保证测试到b数组中最后一个数据之前 
			pp.push(node(q.sum-b[bb]+b[bb+1],bb+1));//因为a数组第一个元素和b数组第一个
			//元素已经保存过了，现在试探b数组第二小元素和a中最小元素组合起来求和
			//能否构造新的最小值，这里利用了优先队列的特点自动排序 
		}
	} 
}
int main()
{
	int n;
	while(cin>>n)
	{
		memset(a,sizeof(a),0);
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				cin>>a[i][j]; 
			}
			sort(a[i],a[i]+n);
		}
		
		for(int i=1;i<n;i++){//因为题目只要求输出前n个最小和 
			merge(a[0],a[i],a[0],n); 
		}
		
		cout<<a[0][0];
		for(int i=1;i<n;i++){
			cout<<" "<<a[0][i];
		}
		cout<<endl;
	}
}