1
/**//*
2
Name: pku2442
3 Copyright:
4 Author: avcpp
5 Date: 13/02/11 22:23
6 Description: heap
7
*/
8
9#include <stdio.h>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <stdlib.h>
14#include <string.h>
15using namespace std;
16class node
17
{
18 public:
19 int val;
20 int row;
21 int col;
22
node(int _val,int _row,int _col):val(_val),row(_row),col(_col){}
23};
24bool operator < (node a,node b)
25{
26 return a.val>b.val;
27}
28vector<int> a[110],temp,temp1;
29priority_queue<node> q;
30bool flag[2010][2010];
31int n,m;
32int main()
33{
34 int cas;
35 scanf("%d",&cas);
36 while(cas--)
37 {
38 for(int i=0;i<110;i++) a[i].clear();
39 temp.clear();
40 scanf("%d %d",&n,&m);
41 for(int i=0;i<n;i++)
42 {
43 for(int j=0;j<m;j++)
44 {
45 int buf;
46 scanf("%d",&buf);
47 a[i].push_back(buf);
48
}
49 sort(a[i].begin(),a[i].end());
50 }
51 temp=a[0];
52 for(int i=1;i<n;i++)
53 {
54 temp1.clear();
55 while(!q.empty()) q.pop();
56 int cnt=0;
57 memset(flag,false,sizeof(flag));
58 q.push(node(a[i][0]+temp[0],0,0));
59 flag[0][0]=true;
60 while(cnt<m)
61 {
62 node buf=q.top();
63 q.pop();
64 temp1.push_back(buf.val);
65 cnt++;
66 if(!flag[buf.row+1][buf.col])
67 {
68 q.push(node(temp[buf.row+1]+a[i][buf.col],buf.row+1,buf.col));
69 flag[buf.row+1][buf.col]=true;
70 }
71 if(!flag[buf.row][buf.col+1])
72 {
73 q.push(node(temp[buf.row]+a[i][buf.col+1],buf.row,buf.col+1));
74 flag[buf.row][buf.col+1]=true;
75 }
76 }
77 temp=temp1;
78 }
79 for(int i=0;i<m;i++)
80 {
81 if(i==m-1) printf("%d\n",temp[i]);
82 else printf("%d ",temp[i]);
83 }
84 }
85 return 0;
86}
87
88
题目可以分解为：
给你两个有序的序列，a1[],a2[]怎么找到前n个最小的两个序列的和。
先将a1[],a2[]排好序，当然是从小到大排，建立一个堆，首先将a1[0]+a2[0]入堆，然后出堆，这个数一定是两个序列和最小的一个，然后将a1[0]+a2[1]和a1[1]+a2[0]入堆，然后出堆，依次类推既可以找到最小的n个和了。
不过有一个问题：比如说a1[1]+a2[0]这个时候出堆了，然后a1[1]+a2[1]入堆，之后a1[0]+a2[1]出堆了，然后a1[1][1]+a2[1][1]又要入堆了，这是错误的，我在这里卡了很久拍了一个10*10的数据才发现，真是大意了，哎。。。。
贴下代码和我的数据，希望有帮助
12
10 10
21 12 123 3 21 123 32 143 43 56
2 32 43 34 54 56 656 76 43 234
234 45 5 65 56 76 43 23 435 57
32 324 435 46 56 76 87 78 43 23
3 32 324 45 56 57 34 23 54 565
23 32 34 342 324 232 2 432 324 12
234 324 4 45 65 67 435 23 5 654
34 3245 345 56 56 657 67 456 345 325
234 234 546 65 88 66 53 654 65 765
5 3 34 34 34 56 345 234 2 34
ans：
131 132 132 133 134 135 140 140 141 141
posted on 2011-02-13 22:26
avcpp 阅读(133)
评论(0) 编辑 收藏 引用