哈夫曼树

题目描述

哈夫曼树，第一行输入一个数n，表示叶结点的个数。需要用这些叶结点生成哈夫曼树，根据哈夫曼树的概念，这些结点有权值，即weight，题目需要输出所有结点的值与权值的乘积之和。

输入

输入有多组数据。 每组第一行输入一个数n，接着输入n个叶节点（叶节点权值不超过100，2<=n<=1000）。

输出

输出权值。

样例输入

2 2 8 3 5 11 30

样例输出

10 62

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<map>
#include<stack>
#include<queue>
#define ll long long
using namespace std;
ll n,ans,h[5020];
struct E{
    ll k,l,r,t;
    friend bool operator < (E x,E y){return x.k>y.k;}
}e[5020];
priority_queue<E>q;
void dfs(ll root){
    if(root==0) return;
    ll ls=e[root].l,rs=e[root].r;
    h[ls]=h[rs]=h[root]+1;
    if(ls==0&&rs==0){
        ans+=e[root].k*h[root];
    }
    dfs(ls);
    dfs(rs);
}
int main(){
    while(cin>>n){
        ll cur=n;ans=0;
        memset(h,0,sizeof(h));
        for(ll i=1;i<=n;i++){
            ll x;
            cin>>x;
            e[i].k=x;
            e[i].l=0;
            e[i].r=0;
            e[i].t=i;
            q.push(e[i]);
        }
        while(q.size()>1){
            E xx=q.top();q.pop();
            E yy=q.top();q.pop();
            //cout<<xx.k<<' '<<yy.k<<endl;
            E neww=(E){xx.k+yy.k,xx.t,yy.t,++cur};
            e[cur]=neww;
            q.push(neww);
        }
        E root=q.top();q.pop();
        h[root.t]=0;
        dfs(root.t);
        /*for(int i=1;i<=cur;i++){
            cout<<e[i].k<<' '<<e[i].l<<' '<<e[i].r<<' '<<e[i].t<<endl;
        }*/
        cout<<ans<<endl;
    }
    return 0;
}