//UVA 11997 - K Smallest Sums
/*
题意：一个k*k数组，每行取一个元素 求和，共有k^k种可能，找到k种最小的和
输出。
第一次是O(n*n)超时了，改用归并排序，优先队列实现，时间降低为nlogn
思路：初始化：每行sort排序；然后每两行合并 优先队列存贮前K小数，继续合并完。
输出前k个元素即可。
*///AC
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int M=800;
int a[M][M];
int k;
struct Node
{
int sum;//a1[i][j]+a2[i+1][j]
int ct;//标记是否到了最后一行和k 比大小
Node(int x , int y):sum(x), ct(y){}
bool operator <(const Node &e)const//重载<
{
return sum>e.sum;//升序排列元素
}
};
int merge(int *A,int *B)
{
int i,j;
priority_queue <Node> s;
for(i=0;i<k;i++)
s.push(Node(A[i]+B[0],0));//元素入队列
for(i=0;i<k;i++)
{
Node node =s.top();//找到队列中最小元素赋值；
s.pop();
A[i]=node.sum;
int ct=node.ct;
if(ct+1<k)//没有扫描到最后一行
s.push(Node(node.sum-B[ct]+B[ct+1],ct+1));//都merge归并为一行记为A
}
}
int main()
{
int i,j;
while(scanf("%d",&k)!=EOF)
{
for(i=0;i<k;i++)
{
for(j=0;j<k;j++)
scanf("%d",&a[i][j]);// sort(a[i],a[i]+k);//
sort(&a[i][0],&a[i][0]+k);
}
for(i=1;i<k;i++)
merge(a[0],a[i]);//每两行归并排序。
for(i=0;i<k-1;i++)
printf("%d ",a[0][i]);
printf("%d",a[0][k-1]);//最后一个数必须独立输出
printf("\n");
}
return 0;
}
//O(n*n)
/*//
//超时
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
using namespace std;
const int M=800;
int n;
int a[M][M],b[M*M];
void f()
{
memset(b,0,sizeof(b));
int i,j,k;
int ct=0,sum=0;
for(i=0;i<n;i++)
ct+=a[i][0];
for(i=0;i<n;i++)
{
for(j=1;j<n;j++)
{
b[sum++]=a[i][j]-a[i][j-1];
}
}sort(b,b+sum);
printf("%d ",ct);
for(i=0;i<n-1;i++)
printf("%d ",ct+b[i]);
printf("\n");
}
int main()
{
int i,j,k;
while(scanf("%d",&n)!=EOF)
{
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
scanf("%d",&a[i][j]);//&b[j]);
}
sort(&a[i][0],&a[i][0]+n);//每行升序排序
//sort(b,b+n);
// printf("##########\n"); //memcpy(&a[i][0],b,sizeof(a));//把a数组全部数字给b，a自己保留。
}f();
}
return 0;
}
*/