[NOI2015]荷马史诗

_Sein · 2018-12-23 15:44:08 · 题解

此题本体为Huffman树

（下文均将huffman树讲为哈夫曼树）

• 哈夫曼树的定义

  哈夫曼树：带权路径长度WPL最短的多叉树（最优多叉树）构造这种树的算法最早是由哈夫曼(Huffman)1952年提出，这种树在信息检索中很有用。

  下面以二叉哈夫曼树为例 给n个点，每个点都有权值，构造一棵哈夫曼树。每次选剩下的两棵根权值最小的树合并成一棵新树，新树的根权值等于两棵合并前树的根权值和。（一开始一个点也看成一棵树，只不过这棵树没有孩子节点）

  例1：4个点，a、b、c、d，权值分别为7、5、2、4。

  构树过程：因为4个点，所以合并3次（n个点，合并n-1次）

  第一步：选根权值最小的两棵树2（c）和4（d）合并，新树的根节点为6，如图(b)；

  第二步：选根权值最小的两棵树5（b）和6合并，新树的根节点为11，如图(c)；

  第三步：选根权值最小的两棵树7（a）和11合并，新树的根节点为18，如图(d)；

  • 基本概念

  树的路径长度PL：从树根到树的每个节点的路径长度（每条边长度为1）之和（完全二叉树为这种路径长度最短的二叉树）。

  树的带权路径长度WPL：树的所有叶子节点的带权路径长度（该节点到根节点路径长度与节点上权的乘积）之和。

  透彻理解树的路径长度和树的带权路径长度这两个概念非常重要。

  • 关于k叉哈夫曼树

  以下选自lyd大佬的话：

  对于k叉哈夫曼树的求解,直观的想法是在贪心的基础上,改为每次从堆中去除最小的k个权值合并。然而，仔细思考可以发现，如果在执行最后一次循环时，堆的大小在（2~k-1）之间（不足以取出k个），那么整个哈夫曼树的根的子节点个数就小于k。这显然不是最优解————我们任意取哈夫曼树中一个深度最大的节点，改为树根的子节点，就会使∑w_i*l_i变小。

  因此，我们应该在执行上述贪心算法之前，补加一些额外的权值为0的叶子节点，使叶子节点的个树满足(n-1)%(k-1)=0。

  • 重中之重：哈夫曼编码

  哈夫曼编码原则： n个节点的哈夫曼树含有2n-1个节点，没有度为1的节点 编码从叶子节点到根节点，译码从根节点到叶子节点。

  从哈夫曼树根节点开始，对左子树分配码“0”，右子树分配码“1”，一直到达叶子节点为止，然后将从树根沿每条路径到达叶子结点的代码排列起来，便得到了哈夫曼编码。

  例子

  一篇电文，原文为：AMCADEDDMCCAD。现在要把原文转换成01串发送给对方。为了节省资源，我们当然希望翻译好的01串长度尽量的短。怎么办？

  研究发现：1、只有5个字母E,M,C,A,D； 2、这5个字母的使用频度分别为｛E,M,C,A,D｝= ｛1,2,3,3,4｝。 用频度为权值生成哈夫曼树，并在叶子上标注对应的字母，在树枝上标注分配码“0”或“1”（注：分配码不是边的长度，而是区分左右孩子代表方向）:

  各字母的编码即为哈夫曼编码： EMCAD 所有编码长度和为12位，即PL=12，此时的PL并不是最小的，但此时的WPL一定是最小的。WPL最小才能使得密报翻译的01串长度最短。

  • 回归本体

  本题所构造的编码其实就是huffman编码（这还用说吗），我们可以把单词的次数作为哈夫曼树叶子节点的权值，求出k叉哈夫曼树就行了。 答案就为所有叶子节点的wpl，最深叶子节点的深度了

  • 代码

    #include<cstdio>
    #include<cstring>
    #include<queue>
    #include<algorithm>
    #define ll long long
    using namespace std;
    struct node
    {
    ll w,h;
    node(){w=0,h=0;}
    node(ll w,ll h):w(w),h(h){}
    bool operator <(const node &a)const{return a.w==w?h>a.h:w>a.w;}
    };
    ll ans;
    priority_queue<node>q;
    int main()
    {
    ll n,k;ans=0;scanf("%lld%lld",&n,&k);
    for(int i=1;i<=n;i++)
    {
    ll w;scanf("%lld",&w);
    q.push(node(w,1));
    }
    while((q.size()-1)%(k-1)!=0)q.push(node(0,1));
    while(q.size()>=k)
    {
    ll h=-1;ll w=0;
    for(int i=1;i<=k;++i)
    {
        node t=q.top();q.pop();
        h=max(h,t.h);
        w+=t.w;
    }
    ans+=w;
    q.push(node(w,h+1));
    }
    printf("%lld\n%lld\n",ans,q.top().h-1);
    return 0;
    }