9度教程第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;
					}
					else
						if(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);
	}
}