九度教程第31题

题目地址：http://ac.jobdu.com/problem.php?cid=1040&pid=30

C语言源码：

#include<stdio.h>typedef struct Huffmantree{int weight,lchild,rchild,parent;}Huffmantree;int depth(Huffmantree H[],int n,int i){int d;d=0;while(H[i].parent!=0){d++;i=H[i].parent;}return d;}void dsort(Huffmantree H[],int m,int num[],int n,int i){int j,key;key=num[i];for(j=2*i+1;j<n;j=2*j+1){if(j+1<n&&H[num[j]].weight>H[num[j+1]].weight)j++;if(H[key].weight<H[num[j]].weight) break;*(num+i)=*(num+j);i=j;}*(num+i)=key;}void adjust(Huffmantree H[],int m,int num[],int n,int i){int key,flag;key=num[i];flag=1;while((i-1)/2>=0&&H[key].weight<H[num[(i-1)/2]].weight){*(num+i)=*(num+(i-1)/2);i=(i-1)/2;if(i==0&&flag)flag=0;elseif(i==0&&flag==0)break;}*(num+i)=key;}int main(){int n,i,w,min1,min2,d[22000],num;Huffmantree H[22000];scanf("%d",&n);while(n){num=n;for(i=0;i<n;i++)scanf("%d",&H[i].weight);for(i=0;i<2*n-1;i++){H[i].lchild=0;H[i].rchild=0;H[i].parent=0;}for(i=0;i<n;i++)d[i]=i;for(i=n/2;i>=0;i--)dsort(H,2*n-1,d,n,i);for(i=n;i<2*n-1;i++){min1=d[0];d[0]=d[num-1];num=num-1;dsort(H,2*n-1,d,num,0);min2=d[0];d[0]=d[num-1];num=num-1;dsort(H,2*n-1,d,num,0);H[i].weight=H[min1].weight+H[min2].weight;H[i].lchild=min1;H[i].rchild=min2;H[min1].parent=i;H[min2].parent=i;d[num++]=i;adjust(H,2*n-1,d,num,num-1);}w=0;for(i=0;i<n;i++)w+=H[i].weight*depth(H,2*n-1,i);printf("%d\n",w);scanf("%d",&n);}}