Poj,3253
//Huffman每次选最小的两个加和最小，最后结果最小。
1 #include <iostream> 2 #include <queue> 3 #include <vector> 4 #include <algorithm> 5 #include <cstdio> 6 7 #define ll long long 8 #define N 20005 9 using namespace std; 10 11 int n; 12 class HTree 13 { 14 public : 15 HTree* left; 16 HTree* right; 17 int weight; 18 19 HTree(){left = right = NULL; weight=0;} 20 HTree(HTree* l,HTree* r,int w){left = l; right = r; weight=w;} 21 ~HTree(){delete left; delete right;} 22 }; 23 24 class Compare_tree 25 { 26 public: 27 bool operator () (HTree* t1, HTree* t2) 28 { 29 return t1->weight> t2->weight; 30 } 31 }; 32 33 ll BuildTree(int *frequency,ll charge) 34 { 35 priority_queue<HTree*,vector<HTree*>,Compare_tree> QTree; 36 37 for (int i=0;i<n;i++) 38 { 39 if(frequency[i]) 40 QTree.push(new HTree(NULL,NULL,frequency[i])); 41 } 42 43 while (QTree.size()>1) 44 { 45 HTree* lc = QTree.top(); 46 QTree.pop(); 47 HTree* rc = QTree.top(); 48 QTree.pop(); 49 charge+=lc->weight+rc->weight; 50 HTree* parent = new HTree(lc,rc,lc->weight+rc->weight); 51 QTree.push(parent); 52 } 53 return charge; 54 } 55 56 int main() 57 { 58 int L; 59 int freq[N] = {0}; 60 scanf("%d",&n); 61 for(int i=0;i<n;i++) 62 { 63 scanf("%d",&L); 64 freq[i]=L; 65 } 66 ll result=BuildTree(freq,0); 67 printf("%lld ",result); 68 return 0; 69 }
1 #include <iostream> 2 #include <queue> 3 #include <algorithm> 4 #include <cstdio> 5 6 #define ll long long 7 #define N 20005 8 using namespace std; 9 10 int n; 11 struct Node 12 { 13 int w; 14 bool operator<(const Node& a)const 15 { 16 return w>a.w; 17 } 18 }; 19 20 int main() 21 { 22 priority_queue<Node> qu; 23 Node root; 24 scanf("%d",&n); 25 for(int i=0;i<n;i++) 26 { 27 28 scanf("%d",&root.w); 29 qu.push(root); 30 } 31 ll result=0; 32 while(qu.size()>1) 33 { 34 int l=qu.top().w;qu.pop(); 35 int r=qu.top().w;qu.pop(); 36 root.w=l+r; 37 result+=root.w; 38 qu.push(root); 39 } 40 printf("%lld ",result); 41 return 0; 42 }
zoj,2399
注意Huffman的数据可能很大，所以注意weight和最后的和都用longlong
Huffman编码的长度等于 w[i]*l[i]就是每次建一次树的跟节点的权值
1 #include <iostream> 2 #include <queue> 3 #include <cstdio> 4 5 using namespace std; 6 7 typedef long long ll; 8 9 struct node 10 { 11 ll w; 12 13 bool operator<(const node& a)const 14 { 15 return w>a.w; 16 } 17 }; 18 19 20 int main() 21 { 22 int size; 23 scanf("%d",&size); 24 while(size--) 25 { 26 int n; 27 priority_queue<node> qp; 28 scanf("%d",&n); 29 for(int i=0;i<n;i++) 30 { 31 int w; 32 cin>>w; 33 node now; 34 now.w=w; 35 qp.push(now); 36 } 37 ll ans=0; 38 while(qp.size()>1) 39 { 40 ll l=qp.top().w;qp.pop(); 41 ll r=qp.top().w;qp.pop(); 42 43 node now1; 44 now1.w=l+r; 45 qp.push(now1); 46 47 ans+=now1.w; 48 } 49 50 printf("%lld ",ans); 51 if(size) 52 printf(" "); 53 } 54 return 0; 55 }
poj,1521
学校系统真是不敢恭维，我感觉在针对我。。。。
交了一个小时都wa，我之后无可奈何跑到poj上去交，一下就过了。。我真的见了鬼了
1 #include <cstdio> 2 #include <iostream> 3 #include <string> 4 #include <queue> 5 #include <cstring> 6 #include <cstdlib> 7 8 using namespace std; 9 const int maxn=256; 10 struct Node 11 { 12 int weight; 13 14 bool operator<(const Node& a)const 15 { 16 return weight>a.weight; 17 } 18 }; 19 20 21 int main() 22 { 23 char s[maxn]; 24 25 while(gets(s)) 26 { 27 if(!strcmp(s,"END")) 28 break; 29 int freq[maxn]={0}; 30 int cnt=strlen(s); 31 priority_queue<Node> pq; 32 for(int i=0;i<cnt;i++) 33 { 34 freq[s[i]]++; 35 } 36 for(int i=0;i<200;i++) 37 { 38 Node now; 39 if(freq[i]) 40 { 41 now.weight=freq[i]; 42 pq.push(now); 43 freq[i]=0; 44 } 45 } 46 47 int ans=0; 48 while(pq.size()>1) 49 { 50 int l=pq.top().weight;pq.pop(); 51 int r=pq.top().weight;pq.pop(); 52 53 Node now; 54 now.weight=l+r; 55 pq.push(now); 56 ans+=now.weight; 57 } 58 if(!ans) 59 ans=cnt; 60 while(!pq.empty()) 61 pq.pop(); 62 printf("%d %d %.1lf ",cnt*8,ans,double((double)(8*cnt)/ans)); 63 } 64 return 0; 65 }