题目链接：点击打开链接
题目大意：验证是否为哈夫曼树。
解题思路：验证哈夫曼树的两个必要条件：
- 非叶子节点Weight之和 == WPL == Li*Wi + ..之和。
- 任何01字符串都不是其他字符串的前缀。
AC 代码
usingnamespacestd; typedeflonglongll; structnode{ intw; strings; }nds[70]; priority_queue<int,vector<int>,greater<int>>pq; unordered_map<char,int>ump; intn; boolok() { for(inti=0;i<n;i++) { stringpre=nds[i].s; for(intj=0;j<n;j++) { if(i!=j&&pre==nds[j].s.substr(0,pre.length())) returnfalse; } } returntrue; } intmain() { intm,wpl=0; charc; scanf("%d ",&n); for(inti=0;i<n;i++) { scanf("%c",&c); scanf("%d ",&ump[c]); pq.push(ump[c]); } while(1) { inttp=pq.top(); pq.pop(); if(pq.empty()) break; tp+=pq.top(); pq.pop(); pq.push(tp); wpl+=tp; } scanf("%d",&m); while(m--) { intsum=0; for(inti=0;i<n;i++) { scanf(" %c",&c); cin>>nds[i].s; nds[i].w=ump[c]; sum+=nds[i].w*nds[i].s.length(); } if(sum==wpl&&ok()) puts("Yes"); elseputs("No"); } return0; }
