하 프 만 트 리 최소 대역 권 경로

//             ，            ，     
#include<stdio.h>
#include<stdlib.h>
int s1,s2;
typedef struct node
{
	int weight;
	int parent;
	int lchild;
	int rchild;
}tree;
void selet(tree ht[],int x)
{
	int i,min1='0x3f',min2='0x3f';
	for(i=1;i<=x;i++)
	{
       if(min1>ht[i].weight&&ht[i].parent==0)
	   {
	     min1=ht[i].weight;
	   }
	}
   for(i=1;i<=x;i++)
	{
       if(min1==ht[i].weight&&ht[i].parent==0)
	   {
	     s1=i;
		 ht[i].parent=-1;
		 break;
	   }
	}
	for(i=1;i<=x;i++)
	{
       if(min2>ht[i].weight&&ht[i].parent==0)
	   {
	     min2=ht[i].weight;
	   }
	}
		for(i=1;i<=x;i++)
	{
       if(min2==ht[i].weight&&ht[i].parent==0)
	   {
	     s2=i;
		 break;
	   }
	}
	ht[s1].parent=0;
	if(min1==min2)
	{
		int r=s1;
		s1=s2;
		s2=r;
	}
	
}
void crthuffmantree(tree ht[],int w[],int n)
{
	int W=0,Q,Y=0;
	for(int i=1;i<=n;i++)
	{
		ht[i].weight=w[i];
		ht[i].parent=0;
		ht[i].lchild=0;
		ht[i].rchild=0;
	}
	int m=2*n-1;
	for(i=n+1;i<=m;i++)
	{
		ht[i].weight=0;
	    ht[i].parent=0;
		ht[i].lchild=0;
		ht[i].rchild=0;
	}
	for(i=n+1;i<=m;i++)
	{
		Q=m-i+1;
		selet(ht,i-1);
	    ht[i].weight=ht[s1].weight+ht[s2].weight;
        Y=Y+ht[i].weight*(Q-1);
		W=W+Q*ht[i].weight;
	    ht[s1].parent=i;
		ht[s2].parent=i;
		ht[i].lchild=s1;
		ht[i].rchild=s2;
	}
	printf("       ：weight,parent,lchild,rchild
");
	for(i=1;i<=m;i++)
	printf("%d %d %d %d
",ht[i].weight,ht[i].parent,ht[i].lchild,ht[i].rchild);
	printf("             : ");
	printf("%d
",W-Y);
}
int main()
{
	tree hufu[400];
	int n,w[100];
	printf("                 : ");
	scanf("%d",&n);
	printf("         : ");
	for(int i=1;i<=n;i++)
		scanf("%d",&w[i]);
	hufu[0].weight=0;
	hufu[0].parent=0;
	hufu[0].lchild=0;
	hufu[0].rchild=0;
	crthuffmantree(hufu,w,n);
	return 0;
}