題意：K個(gè)數(shù)組每組K個(gè)值，每次從一組中選一個(gè)，共K^k種，問前K個(gè)小的。

思路：優(yōu)先隊(duì)列處理多路歸并，每個(gè)狀態(tài)含有K個(gè)元素。詳見劉汝佳算法指南。

1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<stack> 5 #include<queue> 6 #include<vector> 7 #include<map> 8 #include<algorithm> 9 using namespace std; 10 int n; 11 int a[1000][1000]; 12 int b[1000]; 13 int c[1000]; 14 15 struct Item 16 { 17 int s,b; 18 Item(int s,int b):s(s),b(b) 19 { 20 } 21 bool operator < (const Item& rhs) const 22 { 23 return s>rhs.s; 24 } 25 }; 26 void merge(int *a,int *b,int *c,int n) 27 { 28 priority_queue<Item>q; 29 for(int i=0; i<n; i++) 30 q.push(Item(a[i]+b[0],0)); 31 for(int i=0; i<n; i++) 32 { 33 Item item =q.top(); 34 q.pop(); 35 c[i]=item.s; 36 int B=item.b; 37 if(B+1<n) 38 q.push(Item(item.s-b[B]+b[B+1],B+1)); 39 } 40 } 41 42 int main() 43 { 44 while(~scanf("%d",&n)) 45 { 46 for(int i=0; i<n; i++) 47 { 48 for(int j=0; j<n; j++) 49 scanf("%d",&a[i][j]); 50 sort(a[i],a[i]+n); 51 } 52 for(int i=1; i<n; i++) 53 merge(a[0],a[i],a[0],n); 54 printf("%d",a[0][0]); 55 for(int i=1; i<n; i++) 56 printf(" %d",a[0][i]); 57 printf("\n"); 58 } 59 return 0; 60 } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/ITUPC/p/5076307.html

總結(jié)

以上是生活随笔為你收集整理的uva 11997 K Smallest Sums 优先队列处理多路归并问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。