05-树9 Huffman Codes（30 分）
In 1953, David A. Huffman published his paper “A Method for the Construction of Minimum-Redundancy Codes”, and hence printed his name in the history of computer science. As a professor who gives the final exam problem on Huffman codes, I am encountering a big problem: the Huffman codes are NOT unique. For example, given a string “aaaxuaxz”, we can observe that the frequencies of the characters ‘a’, ‘x’, ‘u’ and ‘z’ are 4, 2, 1 and 1, respectively. We may either encode the symbols as {‘a’=0, ‘x’=10, ‘u’=110, ‘z’=111}, or in another way as {‘a’=1, ‘x’=01, ‘u’=001, ‘z’=000}, both compress the string into 14 bits. Another…
这题目确实厉害，要用到好多数据结构
看着太烦了，想想真让我写我肯定写不出，这里介绍C++解决的方法
源程序借鉴前人的博客
优先队列
#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
struct input
{char ch;int weight;
}in[100];//初始序列，确定字符和频率（权重）
struct check
{char ch;string code;
}ck[100];//等待检测的序列
bool cmp(check a,check b){return a.code.size()<b.code.size();//长度从小到大排列
}
int cnt(char ch,int N){
//查找ch这个字符在原始序列中的位置for(int i=0;i<N;i++){if(in[i].ch==ch){return i;}}return -1;
}
bool frontSq(int n){
//先排序，再判断是否有这样的一个string，他是另一个string的前缀sort(ck,ck+n,cmp);for(int i=0;i<n;i++){string temp=ck[i].code;for(int j=i+1;j<n;j++){if(ck[j].code.substr(0,temp.size())==temp) return true;//巧妙的substr}}return false;
}
int main(){int N;cin>>N;priority_queue <int, vector<int>, greater<int> > q;//优先队列 从小到大，方便我们构造霍夫曼树 可将greater改为less，即为从大到小for(int i=0;i<N;i++){cin>>in[i].ch>>in[i].weight;q.push(in[i].weight);}int best=0;//计算霍夫曼的WPLint m=0;while(!q.empty()){int a=0;int b=0;a=q.top();q.pop();if(!q.empty()){b=q.top();q.pop();q.push(a+b);}m=a+b;best+=m;}best-=m;//m多加了一次，cut！// 根据霍夫曼树的构造计算weightint t;cin>>t;while(t--){int cost=0;for(int j=0;j<N;j++){cin>>ck[j].ch>>ck[j].code;cost+=ck[j].code.size()*in[cnt(ck[j].ch,N)].weight;}if(cost==best){if(frontSq(N)){
//可能WPL一样，要从前缀再次判断printf("No\n");}else{printf("Yes\n");}}else{printf("No\n");}}return 0;
}