九度教程第30题

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

C语言源码：

#include<stdio.h>#include<limits.h>typedef struct Huffmantree{int weight,lchild,rchild,parent;}Huffmantree;int depth( Huffmantree H[],int n,int x){int d=0;while(H[x].parent!=0){d++;x=H[x].parent;}return d;}int main(){int n,i,min1,fmin1,min2,fmin2,j,w;Huffmantree H[20001];while(scanf("%d",&n)!=EOF){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=n;i<2*n-1;i++){fmin1=-1;min1=INT_MAX;fmin2=-1;min2=INT_MAX;for(j=0;j<i;j++){if(H[j].parent==0){if(H[j].weight<min1){fmin2=fmin1;min2=min1;fmin1=j;min1=H[j].weight;}elseif(H[j].weight<min2){fmin2=j;min2=H[j].weight;}}}H[i].weight=min1+min2;H[i].lchild=fmin1;H[i].rchild=fmin2;H[fmin1].parent=i;H[fmin2].parent=i;}w=0;for(i=0;i<n;i++)w+=H[i].weight*depth(H,2*n-1,i);printf("%d\n",w);}}