poj 2442 优先队列+多路归并 uva 11997

白书上的例题，很是经典。

poj 2442

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <cstdio>
 5 #include <queue>
 6 using namespace std;
 7 
 8 const int M = 100;
 9 const int N = 2000;
10 int a[M][N];
11 
12 struct Node
13 {
14     int j, v;
15     Node(){}
16     Node( int _j, int _v )
17     {
18         j = _j, v = _v;
19     }
20     bool operator < ( const Node & o ) const
21     {
22         return v > o.v;
23     }
24 };
25 
26 void merge_list( int * a, int * b, int len )
27 {
28     priority_queue<Node> q;
29     for ( int i = 0; i < len; i++ )
30     {
31         q.push( Node( 0, a[i] + b[0] ) );
32     }
33     for ( int i = 0; i < len; i++ )
34     {
35         Node node = q.top();
36         q.pop();
37         a[i] = node.v;
38         if ( node.j + 1 < len )
39         {
40             q.push( Node( node.j + 1, node.v - b[node.j] + b[node.j + 1] ) );
41         }
42     }
43 }
44 
45 int main ()
46 {
47     int t;
48     scanf("%d", &t);
49     while ( t-- )
50     {
51         int m, n;
52         scanf("%d%d", &m, &n);
53         for ( int i = 0; i < m; i++ )
54         {
55             for ( int j = 0; j < n; j++ )
56             {
57                 scanf("%d", &a[i][j]);
58             }
59             sort( a[i], a[i] + n );
60         }
61         for ( int i = 1; i < m; i++ )
62         {
63             merge_list( a[0], a[i], n );
64         }
65         for ( int i = 0; i < n; i++ )
66         {
67             printf("%d", a[0][i]);
68             if ( i != n - 1 ) putchar(' ');
69             else putchar('
');
70         }
71     }
72     return 0;
73 }

uva 11997

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <cstdio>
 5 #include <queue>
 6 using namespace std;
 7 
 8 const int N = 1000;
 9 int a[N][N];
10 
11 struct Node
12 {
13     int j, v;
14     Node(){}
15     Node( int _j, int _v )
16     {
17         j = _j, v = _v;
18     }
19     bool operator < ( const Node & o ) const
20     {
21         return v > o.v;
22     }
23 };
24 
25 void merge_list( int * a, int * b, int len )
26 {
27     priority_queue<Node> q;
28     for ( int i = 0; i < len; i++ )
29     {
30         q.push( Node( 0, a[i] + b[0] ) );
31     }
32     for ( int i = 0; i < len; i++ )
33     {
34         Node node = q.top();
35         q.pop();
36         a[i] = node.v;
37         if ( node.j + 1 < len )
38         {
39             q.push( Node( node.j + 1, node.v - b[node.j] + b[node.j + 1] ) );
40         }
41     }
42 }
43 
44 int main ()
45 {
46     int n;
47     while ( scanf("%d", &n) != EOF )
48     {
49         for ( int i = 0; i < n; i++ )
50         {
51             for ( int j = 0; j < n; j++ )
52             {
53                 scanf("%d", &a[i][j]);
54             }
55             sort( a[i], a[i] + n );
56         }
57         for ( int i = 1; i < n; i++ )
58         {
59             merge_list( a[0], a[i], n );
60         }
61         for ( int i = 0; i < n; i++ )
62         {
63             printf("%d", a[0][i]);
64             if ( i != n - 1 ) putchar(' ');
65             else putchar('
');
66         }
67     }
68     return 0;
69 }