這題是給k個大小為k的array，每個array挑一個數字再總和，求k個最小的總和。
由於題目總共會有k的k次方種總和，所以用暴力解的話一定會TLE。
我們可以推出在k列中的任意兩列一定對答案有貢獻，例如任意兩列選兩個數字出來總和也一定是最小，所以我們可以逐列求出答案出來，首先要先將每一列排序，假設前兩列為A跟B，那我們可以先將a1+b1,a2+b1,a3+b1...ak+b1放到min heap裡面，a1+b1一定是最小的，所以先pop出來，這時候我們可以將a1+b2放到heap中，因為如果我們放的是其他組合的話，在heap裡面一定會有數字是更小的(例如我們放a2+b2，但是heap裡面的a2+b1是更小的)，而a2+b2 = (a1+b1)+b2-b1，a1+b1是本來pop出來的值，有一個規律是每次變更的都會是b的index，pop k次之後，就可以求出這兩行裡面的k個最小值，照這樣的作法逐行求取k個最小的值。
//ignore header files
struct element{
int sum,index;
element(int x,int y){
sum = x;
index = y;
}
bool operator<(const element & e) const{
return sum>e.sum;
}
};
int k;
void merge(int *,int *);
int main(int argc, char const* argv[])
{
int c[800][800];
while(scanf("%d",&k) != EOF){
for(int i = 0;i<k;i++){
for(int j = 0;j<k;j++){
scanf("%d",&c[i][j]);
}
sort(c[i],c[i]+k);
}
//priority_queue<element> pq;
for(int i = 1;i<k;i++){
//逐行找k個最小的
merge(c[0],c[i]);
}
printf("%d",c[0][0]);
for(int i = 1;i<k;i++){
printf(" %d",c[0][i]);
}
printf("\n");
}
return 0;
}
void merge(int *a,int *b){
priority_queue<element> pq;
for(int i = 0;i<k;i++)
pq.push(element(a[i]+b[0],0));
//pop k次之後，"目前"的k個最小的也決定好了
for(int i = 0;i<k;i++){
element e = pq.top();
pq.pop();
a[i] = e.sum;
pq.push(element(e.sum-b[e.index]+b[e.index+1],e.index+1));
}
}