[NOI2015]荷马史诗 - Huffman树

简化题意： 构造一棵包含n个叶子节点的 $k$ 叉树 , 第 $i$ 个叶子节点深度为 $dep[i]$ , 权值为 $w[i]$ 。 $1.$ 最小化 $\sum_{i=1}^n w[i] \times dep[i]$ . $2.$ 在满足此条件下 , 最小化 $max_{i=1}^n{dep[i]}$ . 先来说明简化后的题意与原问题等价：设每个字母代表树中的一个结点，又因为每个单词都以一个叶子结束，所以保证了单词互不相同。 考虑条件$1$ , 满足此条件的树叫 **最优二叉树** , 别称 **Huffman** 树 。 先考虑 $k=2$ 的情况，我们可以贪心让权值小的叶子深度尽量大。 自下而上建树，具体步骤如下： 1. 将 n 个叶子节点插入一个小根堆。 2. 取出2个权值最小的叶子 a, b ，新建一个结点 c ，则： - c为Huffman树上点a,b的父亲 - w[c]=w[a]+w[b] 3. 将c插入小根堆，重复执行 2 操作直至 n=1 。 至此，$k=2$ 的情况已经得到解决，下面考虑 $k>2$ 的情况。 上述贪心不能解决 $k>2$ 的情况，是因为最后一次 $2$ 操作可能 $n<k$ 导致此时从任意一层取一个叶子节点到该层都比此方案优。 解决这个问题的方案为：虚拟添加若干个权值为 $0$ 的叶子结点，使得 $(n-1) \mod (k-1)=0$ ，上述问题得以解决。 再考虑条件$2$：记录每个结点子树的深度，在权值相等的结点中，选择子树深度较小的结点合并即可。 下面贴 [[NOI2015]荷马史诗](https://www.luogu.com.cn/problem/P2168) 的代码 ```cpp #include<iostream> #include<cstdio> #include<queue> using namespace std; const int N=1002019; #define int long long int n,k,ans,mxd,tot,val[N],v[N]; struct Edge{int to,next;}e[N<<1]; void add(int x,int y){ e[++tot].to=y; e[tot].next=v[x]; v[x]=tot; } struct node{ int id,w,dep; // id :编号, w :权值, dep :子树深度 . node(int a,int b,int c){id=a;w=b;dep=c;}; bool operator >(const node &rhs)const{ return rhs.w==w?rhs.dep<dep:rhs.w<w; } }; priority_queue<node,vector<node>,greater<node> > q; void dfs(int x,int d){ // 统计答案 if(x<=n)ans+=val[x]*d,mxd=max(mxd,d); for(int p=v[x];p;p=e[p].next)dfs(e[p].to,d+1); } int read(){ int x=0,f=1; char ch=getchar(); while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } #undef int int main() { #define int long long n=read(); k=read(); for(int i=1;i<=n;i++) q.push(node(i,val[i]=read(),0)); while((n-1)%(k-1)!=0)q.push(node(++n,0,0)); // 插入若干虚拟结点 int id=n,n1=n; while(n1-=k-1,n1>=1){ int th=0,mx=0; ++id; // 新建编号为 id 的点 th for(int i=1;i<=k;i++,q.pop()){ // 取出 k 个最优元素 node nw=q.top(); th+=nw.w; mx=max(mx,nw.dep); add(id,nw.id); } q.push(node(id,th,mx+1)); // 插入该结点 } dfs(id,0); // 统计答案 printf("%lld\n%lld",ans,mxd); return 0; } ```