一般最小代价树 noj 1081.txt

ACM资料大集合

#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;

#define MAX 1000000000
#define NMAX 10005

int w[NMAX*2];
int flag[NMAX*2];
、
//一般最小代价树 NOJ 1081
//用霍夫曼编码方法解决
/*
输入：
5
1 1 1 1 5

输出：
17
*/
long cal(long num)
{
	int i,j,min1,min2,minnum1,minnum2,sum=0;
	for(i=1;i<=num*2;i++) flag[i]=1;//开始都是可用的
	for(i=0;i<num-1;i++)
	{
		min1=MAX;
		min2=MAX;
		for(j=1;j<=num+i;j++)
		{
			if(flag[j]==1&&(min1>w[j]||min2>w[j])) 
			{	//求出可用序列中最小的两个数
				if(min1>min2) {min1=w[j];minnum1=j;}
				else {min2=w[j];minnum2=j;}
			}
		}
		w[num+i+1]=min1+min2;//类似贪心思想，每次取最小代价的两个节点合成新树
		sum+=w[num+i+1];
		flag[minnum1]=0;//用过了，下次不能再用了
		flag[minnum2]=0;//同上
	}
	return sum;
}

int main()
{
	int num,i;
	while(scanf("%d",&num)!=EOF)
	{
		for(i=1;i<=num;i++)
			scanf("%d",&w[i]);
		cout<<cal(num)<<endl;
	}
	return 0;
}