哈夫曼树，第一行输入一个数n，表示叶结点的个数。需要用这些叶结点生成哈夫曼树，根据哈夫曼树的概念，这些结点有权值，即weight，题目需要输出所有结点的值与权值的乘积之和。
- 输入：
输入有多组数据。
每组第一行输入一个数n，接着输入n个叶节点（叶节点权值不超过100，2<=n<=1000）。
- 输出：
输出权值。
- 样例输入：
5
1 2 2 5 9
- 样例输出：
37
#include<stdio.h>
struct huffman
{
int weight;
int parent,lchild,rchild;
}list[];
int main(){
int n,i,j,ans,lnode,rnode,m1,m2;
while(~scanf("%d",&n)){
for(i=;i<*n-;i++)//所有节点的相关域初值为-1
list[i].parent=list[i].lchild=list[i].rchild=-;
for(i=;i<n;i++)
scanf("%d",&list[i].weight);
ans=;
for(i=n;i<*n-;i++){//构建哈夫曼树
lnode=rnode=;
m1=m2=;
for(j=;j<i;j++){
if(list[j].weight<m1&&list[j].parent==-){
rnode=lnode;
m2=m1;
lnode=j;
m1=list[j].weight;
}
else if(list[j].weight<m2&&list[j].parent==-){
rnode=j;
m2=list[j].weight;
}
}
list[lnode].parent=i;list[rnode].parent=i;
list[i].lchild=lnode;list[n+i].rchild=rnode;
list[i].weight=list[lnode].weight+list[rnode].weight;
ans+=list[i].weight;
}
printf("%d\n",ans);
}
}