kmt.cpp

给定一棵有向树Ｔ

#include<stdio.h>
#include<iostream>

using namespace std;

int n,k;

typedef struct binode *link;
link *subtree;

//二叉树的结点结构如下
class binode
{
public:
	int w,d,dep;
	int **cost,*dis;
	link parent,left_child,right_child;
};

//创建一个新结点
link newnode()
{
	link p=new binode;
	p->parent=0;p->left_child=0;p->right_child=0;
	p->w=0;p->d=0;p->dep=0;
	return p;
}

//找出新结点的插入位置
link find_insert_position(link q)
{
	while(q&&q->right_child) q=q->right_child;
	return q;
}

//前序遍历
void PreOrder(void(*Visit)(link u),link t)
{
	if(t)
	{
		Visit(t);
		PreOrder(Visit,t->left_child);
		PreOrder(Visit,t->right_child);
	}
}

//二维数组的初始化
void Make2DArray(link t,int k,int dep)
{
	t->cost=new int *[k];
	for(int i=0;i<k;i++)
		t->cost[i]=new int[dep];
}

//计算结点t的dep和dis的值
void get_dep(link t)
{
	if(t->parent) t->dep=t->parent->dep+1;
	t->dis=new int[t->dep+1];
	t->dis[0]=0;
	if(t->parent)
		for(int i=1;i<=t->dep;i++)
			t->dis[i]=t->parent->dis[i-1]+t->d;
}

//以前序遍历的方式计算各结点的dep和dis的值
void get_dis_dep(link t)
{
	PreOrder(get_dep,t);
}

//用于构造与给定的树等价的二叉树
void init()
{
	int a,b,c,i;
	scanf("%d%d",&n,&k);
	subtree=new link[n+1];
	for(i=0;i<=n;i++)  subtree[i]=newnode();
	for(i=1;i<=n;i++)
	{
		scanf("%d%d%d",&a,&b,&c);
		subtree[i]->w=a;
		subtree[i]->d=c;
		link p=find_insert_position(subtree[b]);
		link q=newnode();
		p->left_child=subtree[i];p->right_child=q;
		subtree[i]->parent=p;q->parent=p;
	}
	get_dis_dep(subtree[0]);
}

//用于当前结点t的动态规划计算
void comp(link t)
{
	Make2DArray(t,k+1,t->dep+1);
	if(!t->left_child)
	{
		for(int j=0;j<=t->dep;j++)//叶结点转移服务需求时所需要的费用
		{
			t->cost[0][j]=t->w*t->dis[j];
		}
		for(int i=1;i<=k;i++)//在叶结点处增设服务机构，不转移服务需求时的转移费用为0
			for(int j=0;j<=t->dep;j++)
				t->cost[i][j]=0;
	}
	else
	{
		for(int i=0;i<=k;i++)//k为增设的服务机构的个数
			for(int j=0;j<=t->dep;j++)// 获得不转移和转移服务需求所需要的转移费用中最小的值
			{
				if(i)  t->cost[i][j]=t->cost[i-1][0];//初始化为增设服务机构为i-1个时在结点t处的值
				else t->cost[i][j]=INT_MAX;//还没增设服务机构时，初始化为一个大的数INT_MAX;
				for(int a=0;a<=i;a++)//获得当前增设服务机构为i个时的最小值
				{
					int tmp=t->left_child->cost[a][j+1]+t->right_child->cost[i-a][j+1]+t->w*t->dis[j];
					if(t->cost[i][j]>tmp)  t->cost[i][j]=tmp;
				}

			}
	}
}

//后序遍历
void PostOrder(void(*Visit)(link u),link t)
{
	if(t)
	{
		PostOrder(Visit,t->left_child);
		PostOrder(Visit,t->right_child);
		Visit(t);
	}
}

//用后序遍历的方式完成整棵树的动态规划计算
int solution()
{
	PostOrder(comp,subtree[0]);
	return subtree[0]->cost[k][0];
}

//主函数
int main()
{
	freopen("input.txt","r",stdin);    
	freopen("output.txt","w",stdout);  
	init();
	printf("%d\n",solution());
	return 0;
}