又是啃课件的一天
定义
构造一棵含 \(n\)个叶子结点的 \(k\)叉树, 其中第 \(i\)个叶子结点权值 \(w_i\), 要求最小化
\(\sum w_i*d_i\), \(d_i\)表示 \(i\)结点的深度.
这样的合法的树被称为 (k 叉)\(Huffman\) 树
构造方法
增加一些叶子结点为 \(0\)的结点, 使得它成为满 \(k\)叉树. 将 \(w\)都丢进小根堆, 每次都
取前 \(k\)小的 \(w\), 和为 \(s\), 建立权值为 \(s\)的节点 \(p\), 令 \(p\)成为这 \(k\)个结点的父亲, 然后把 \(s\)丢入堆.
证明大概就是要保证权值最小在下面, 但是如果不是满 \(k\)叉树会错, 于是就补几个 \(0\)\(qwq\)
感性理解下
应用
这个可以压缩文件的, 不过打不过专业软件就对了.
Problem1 NOIP2004 合并果子 https://www.luogu.org/problem/P1090
想不到吧, 二叉 Huffman 树就可以了, 二叉并不用补 0.
- /*
- @Date : 2019-09-06 21:56:05
- @Author : Adscn ([email protected])
- @Link : https://www.cnblogs.com/LLCSBlog
- */
- #include<bits/stdc++.h>
- #include<bits/extc++.h>
- using namespace std;
- #define IL inline
- #define RG register
- #define gi getint()
- #define gc getchar()
- #define File(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
- template<typename T>IL bool chkmax(T &x,const T &y){return x<y?x=y,1:0;}
- template<typename T>IL bool chkmin(T &x,const T &y){return x>y?x=y,1:0;}
- IL int getint()
- {
- RG int xi=0;
- RG char ch=gc;
- bool f=0;
- while(!isdigit(ch))ch=='-'?f=1:f,ch=gc;
- while(isdigit(ch))xi=xi*10+ch-48,ch=gc;
- return f?-xi:xi;
- }
- template<typename T>
- IL void pi(T k,char ch=0)
- {
- if(k<0)k=-k,putchar('-');
- if(k>=10)pi(k/10,0);
- putchar(k%10+'0');
- if(ch)putchar(ch);
- }
- __gnu_pbds::priority_queue<int,greater<int>>p;
- int main(void)
- {
- int n=gi;
- for(int i=1;i<=n;++i)p.push(gi);
- int ans=0;
- while(p.size()>=2){
- int w1=p.top();p.pop();
- int w2=p.top();p.pop();
- int s=w1+w2;
- ans+=s;
- p.push(s);
- }
- pi(ans);
- return 0;
- }
Problem2 NOI2015 荷马史诗 https://www.luogu.org/problem/P2168
k 叉 Huffman 树, 维护一下深度就可以了.
所以这玩意除了裸题有什么别的用?
- /*
- @Date : 2019-09-06 22:03:12
- @Author : Adscn ([email protected])
- @Link : https://www.cnblogs.com/LLCSBlog
- */
- #include<bits/stdc++.h>
- #include<bits/extc++.h>
- using namespace std;
- #define IL inline
- #define RG register
- #define gi getint()
- #define gc getchar()
- #define File(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
- template<typename T>IL bool chkmax(T &x,const T &y){return x<y?x=y,1:0;}
- template<typename T>IL bool chkmin(T &x,const T &y){return x>y?x=y,1:0;}
- typedef long long ll;
- IL ll getint()
- {
- RG ll xi=0;
- RG char ch=gc;
- bool f=0;
- while(!isdigit(ch))ch=='-'?f=1:f,ch=gc;
- while(isdigit(ch))xi=xi*10+ch-48,ch=gc;
- return f?-xi:xi;
- }
- template<typename T>
- IL void pi(T k,char ch=0)
- {
- if(k<0)k=-k,putchar('-');
- if(k>=10)pi(k/10,0);
- putchar(k%10+'0');
- if(ch)putchar(ch);
- }
- typedef pair<ll,int> pll;
- __gnu_pbds::priority_queue<pll,greater<pll>>q;
- #define fi first
- #define se second
- #define mp make_pair
- int main(void)
- {
- int n=gi,k=gi;
- for(int i=1;i<=n;++i)q.push(mp(gi,0));
- while((n-1)%(k-1))q.push(mp(0,0)),++n;
- ll ans=0;
- while(n>1){
- ll sum=0;
- int mh=0;
- for(int i=1;i<=k;++i)sum+=q.top().fi,chkmax(mh,q.top().se),q.pop();
- ans+=sum;
- q.push(mp(sum,mh+1));
- n-=k-1;
- }
- pi(ans,'\n'),pi(q.top().se);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3186444.html