#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

typedef struct CElement{
	int sum,pos;
}CElement;

int data[2][2001];
int a2b[2001];
CElement minHeap[2001];

//自己写的堆，测试发现比stl的优先队列要快那么100多ms……囧……
void add(int sum,int pos){
	int hole=(++minHeap[0].sum);
	while(hole!=1 && minHeap[hole/2].sum>sum){
		minHeap[hole]=minHeap[hole/2];
		hole/=2;
	}
	minHeap[hole].sum=sum;
	minHeap[hole].pos=pos;
}

CElement popMin(){
	CElement ret;
	if(minHeap[0].sum)ret=minHeap[1];
	CElement tmp=minHeap[minHeap[0].sum--];
	int pa=1,child;
	while(pa*2<=minHeap[0].sum){
		child=pa*2;
		if(child+1<=minHeap[0].sum && minHeap[child+1].sum<minHeap[child].sum)child++;
		if(minHeap[child].sum<tmp.sum){
			minHeap[pa]=minHeap[child];
			pa=child;
		}
		else break;
	}
	minHeap[pa]=tmp;
	return ret;
}

//此处是算法的核心，求数组a和b的两两之和的前n小元素，放入数组c中。
//用一个额外数组a2b保留a与b数组元素的映射关系，例如a2b[1]=1,指的是a数组第一个元素将于b数组第一个元素求和。每次从堆里弹出一个元素，就要将相应的a2b自增1，求和后再放入堆中，同时根据a2b是否为1判断是否要添加下一个元素。初始数组是有序的，这样就保证每次添加的元素都是当前可能的最小和。这样，每次最多求2次和，一共有n次，故将求和运算这一块的复杂度从O(n^2)降为O(2n)
void nMinSum(int a[],int b[],int c[],int len){
	int count=0;
	CElement tmp;
	memset(a2b,0,sizeof(a2b));
	memset(minHeap,0,sizeof(minHeap));
	a2b[1]=1;
	add(a[1]+b[1],1);
	while(count!=len){
		tmp=popMin();
		c[++count]=tmp.sum;
		if(count==len)break;
		if(a2b[tmp.pos]==1){
			a2b[tmp.pos+1]=1;
			add(a[tmp.pos+1]+b[1],tmp.pos+1);
		}
		a2b[tmp.pos]++;
		add(a[tmp.pos]+b[a2b[tmp.pos]],tmp.pos);
	}
}

int main(){
	//freopen("in.txt","r",stdin);
	
	int T,m,n;
	int i,j;
	int sum[2001];
	scanf("%d",&T);
	while(T--){
		memset(data,0,sizeof(data));
		memset(sum,0,sizeof(sum));
		scanf("%d %d",&m,&n);
		for(i=0;i<m;i++){
			for(j=1;j<=n;j++){
				scanf("%d",&data[i%2][j]);
			}
			sort(data[i%2]+1,data[i%2]+n+1);
			if(i!=0){
				if(i%2)nMinSum(data[i%2-1],data[i%2],sum,n);
				else nMinSum(data[i%2+1],data[i%2],sum,n);
				for(j=1;j<=n;j++)data[i%2][j]=sum[j];
			}
		}
		i=(i-1)%2; 
		for(j=1;j<=n;j++)printf("%d ",data[i][j]);//此处一定要注意！考虑到m=1的情形，不能直接打印sum数组，而是要打印data[m-1]数组。正是在此处白白贡献了十多次WA！！！ 
		printf("\n");
	}
	
	return 0;
}

• 短小 (931) threedonkey 2012-02-12 20:51:31