题目链接：
Huffman codes
题意：
先给出N个节点的出现次数
再给出M种编码方式
判断每种编码方式是否能构成哈夫曼树
题解：
判断哈夫曼编码的条件有两个：
1 哈夫曼编码不唯一，，但它的WPL(带权路径长度)一定唯一
2 短码不能是长码的前缀
首先可以使用STL优先队列 根据 WPL=所有非叶节点的权值之和 求出标准的WPL1
再根据WPL2=所有叶节点的高度*权值之和
再单独判断是否编码中构成前缀
两个条件都满足则输出Yes
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<queue>using namespace std;struct node1{char ch;int num;}aa[105];struct node2{char ch;string str;}bb[105];int n;int cmp(node2 a,node2 b){return a.str.size()<b.str.size();}int pos(char a){for(int i=1;i<=n;i++)if(aa[i].ch==a)return i;}int judge(){//判断是否有前缀sort(bb+1,bb+1+n,cmp);for(int i=1;i<=n;i++){string t=bb[i].str;for(int j=i+1;j<=n;j++)if(bb[j].str.substr(0,t.size())==t)return 1;}return 0;}int main(){int m,ans1=0,ans2;scanf("%d",&n);priority_queue< int,vector<int>,greater<int> >q;for(int i=1;i<=n;i++){cin>>aa[i].ch>>aa[i].num;q.push(aa[i].num);}int a,b;while(!q.empty()){a=q.top();q.pop();if(!q.empty()){ //最后队列中只会剩下一个根节点b=q.top();q.pop();q.push(a+b);}ans1+=a+b;}ans1=ans1-a-b;// WPL=所有非叶节点的权值之和scanf("%d",&m);while(m–){ans2=0;for(int i=1;i<=n;i++){cin>>bb[i].ch>>bb[i].str;ans2+=aa[pos(bb[i].ch)].num*bb[i].str.size(); //WPL2=所有叶节点的高度*权值之和}if(ans2!=ans1)cout<<"No"<<endl;else if(judge())cout<<"No"<<endl;elsecout<<"Yes"<<endl;}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
原来和文字沾上边的孩子从来都是不快乐的，
