题意：给定一个 k*k 的矩阵，要求你每行选一个数，把他们相加得到 k^k 个和。输出最小的 k 个和。(k<=750, 多组数据)

分析:

首先我们从一个简单的问题入手。如果只有 2 行，每行 k 个数，最小的 k 个和怎么求？

先将这两行的数字升序排序, 设第一行为数组 A，第二行为 B，构成前 k 小的数对的集合为 W，可能成为前 k 小的数对的集合为 P，没有使用过的数对的集合为 Q，（注意 PQ 一定互为补集，所以程序中要确保这一点，防止数对重复取出）那么一开始，W={}, P={(A1,B1)}, Q=U-P. 第一轮：由于 P 中唯一的数对为绝对最小的数对且 W 未满，所以将 P 中最小的数对取出放入 W 中。将 Q 中的 (A1,B2) 及 (A2,B1) 取出放入 P 中。第二轮：将 P 中最小的数对 (Ai,Bi) 取出，放入 W 中，Q 中的 (A[i+1],Bi)、(Ai,B[i+1]) 若存在，则放入 P 中。以此类推。

但是完全没有这么麻烦。

由于 A 和 B 的单调性，对于任意的 Ai，(A[i]+B[j]) 也是存在单调性的。所以上面的问题可以转化为将 k 个数组

{A1+B1,A1+B2,A1+B3…}

{A2+B1,A2+B2,A2+B3…}

{A3+B1,A3+B2,A3+B3…}

…

{Ak+B1,Ak+B2,Ak+B3…} 归并为一个递增序列并取前 k 项。

所以相比于上一个方法，W P Q 这几个集合仍然代表相同的意思，但是转移的方式变简单了：将 P 中最小的数对 (Ai,Bi) 取出，放入 W；将 (Ai,Bi) 所在的数组（就是那 k 个中的一个）中的下一个 (Ai,Bi+1) 放入 P，重复 k 次完成归并。

从理论到实际，也就是 P 集合用优先队列代替，模拟上述归并过程，时间复杂度 O(k²·log₂k)

现在再将两个数组的情况推广到 k 个数组。仅仅一步之遥。将所有的数组按照上述方法归并 (k-1) 次就是答案数组。

#include <queue>
#include <cstdio>
#include <algorithm>

using namespace std;

int ar[1000][1000],ans[1000];

struct node
{
    int a,b,n;
    bool operator < (const node &ths)const{
        return n>ths.n;
    }
};

void ad(int *tar,int *a,int *b,int k)
{
    priority_queue<node> p;
    node tmp,now;
    for(int i=1;i<=k;i++)ans[i]=0;
    for(int i=1;i<=k;i++)
    {
        tmp.a=i,tmp.b=1,tmp.n=a[i]+b[1];
        p.push(tmp);
    }
    for(int i=1;i<=k;i++)
    {
        now=p.top();
        ans[i]=now.n,tmp.a=now.a,tmp.b=now.b+1,tmp.n=a[tmp.a]+b[tmp.b];
        p.pop(),p.push(tmp);
    }
    for(int i=1;i<=k;i++)tar[i]=ans[i];
}

int main()
{
    int k;
    while((scanf("%d",&k))!=EOF)
    {
        for(int i=1;i<=k;i++)for(int j=1;j<=k;j++)scanf("%d",&ar[i][j]);
        for(int i=1;i<=k;i++)sort(ar[i]+1,ar[i]+k+1);
        for(int i=2;i<=k;i++)ad(ar[1],ar[1],ar[i],k);
        for(int i=1;i<=k;i++)if(i==1)printf("%d",ar[1][i]);else printf(" %d",ar[1][i]);
        printf("\n");
    }
    return 0;
}