题目大意：
有一个n*n的矩阵
从每行里选出一个数，有nn种选法，求所有选法中选出数和的最小的n种（重复的算多次）
思路：
首先我们可以知道若已知前两行的最优n种选法
则选完第三行，最优n种选法还是由着n种加上第三行的某个数
这样我们就可以使用一个数组来记录前几行的最优n种选法
然后对于每个要选的行
我们先对于原数组中的每个数都加上该行最小的数加入优先队列
每次从队列里取出一个数，就把它加上的数换成它下一个比它大的
这样每行都加一遍 就可以了
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<algorithm> 5 #include<cstring> 6 #include<cstdlib> 7 #include<queue> 8 #include<vector> 9 #include<set> 10 #include<stack> 11 #define inf 2147483611 12 #define ll long long 13 #define MAXN 760 14 using namespace std; 15 inline int read() 16 { 17 int x=0,f=1; 18 char ch=getchar(); 19 while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();} 20 while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();} 21 return x*f; 22 } 23 int n,map[MAXN][MAXN],ans[MAXN]; 24 struct data 25 { 26 int val,pos; 27 bool operator < (const data &a) const 28 { 29 return val>a.val; 30 } 31 }; 32 int main() 33 { 34 while(scanf("%d",&n)!=EOF) 35 { 36 for(int i=1;i<=n;i++) 37 { 38 for(int j=1;j<=n;j++) map[i][j]=read(); 39 sort(map[i]+1,map[i]+n+1); 40 if(i==1) memcpy(ans,map[1],sizeof(map[1])); 41 } 42 for(int i=2;i<=n;i++) 43 { 44 priority_queue <data> q; 45 for(int j=1;j<=n;j++) q.push((data) {ans[j]+map[i][1],1}); 46 for(int j=1;j<=n;j++) 47 { 48 data tmp=q.top(); 49 q.pop(); 50 ans[j]=tmp.val; 51 if(tmp.pos<n) q.push((data) {tmp.val-map[i][tmp.pos]+map[i][tmp.pos+1],tmp.pos+1}); 52 } 53 } 54 printf("%d",ans[1]); 55 for(int i=2;i<=n;i++) printf(" %d",ans[i]); 56 printf(" "); 57 } 58 }