kthtree.cpp

kthtree问题 给定一棵有向树T

#include <iostream.h>
#include <fstream.h>
#include <stdlib.h>

// w[i]表示i节点的权值
// p[i]表示从i节点出发的有向边所指向的节点号
// d[i]表示从i节点出发的有向边的权值
// s[i][j][p]表示判断在拥有i个服务机构的前j项中，节点标号为p的节点是否为服务机构

ofstream fos;              // 定义输出文件

// 该函数使用动态规划思想，用于计算运输费用值
int thtree(int n, int k, int * w, int *p, int *d, int ***s)
{
	if ( n<k || k<1 ) return 0;

// 建立记录运输费用值的数组并初始化
	int **b=new int *[k+1]; // 动态创建二维数组用来存放I个服务点J个顶点的费用
	for (int i=0; i<=k; i++)
		b[i]=new int[n+1];

	for (i=0; i<=k; i++)  b[i][0]=0;

	b[0][1]=w[1]*d[1];
	for (int j=2; j<=n; j++)  
	{
		int len=0;
		int m=j;
		while (p[m]!=0)
		{
			len+=d[m];
			m=p[m];
		}
		len+=d[m];
		b[0][j]=b[0][j-1]+len*w[j];
	}

// 记录运输费用以及更改并记录服务机构标记 i表示服务点数j表示顶点数
	for (i=1; i<=k; i++)
		for (int j=1; j<=n; j++)
			if (j>i)    // 所增加j节点不是服务机构时的费用
			{
				int len=0;
			    int m=j;
			    while (s[i][j-1][p[m]]!=1) 
				{
		    		len+=d[m];
		        	m=p[m];
				}

		    	len+=d[m];

				int temp=len*w[j]+b[i][j-1];

			//	fos<<i<<":"<<j<<" "<<len<<" "<<temp<<" "<<" "<<b[i][j-1]<<" "<<b[i-1][j-1]<<endl;

				
		 
				
				if (s[i][j-1][p[j]]!=1)
				{
						int t=p[j]; 
						int lenth=0;
						while (s[i-1][j-1][p[t]]!=1)  
						{
							lenth+=d[t];
							//fos<<lenth<<" "<<t<<endl;
							t=p[t];
						}
						lenth+=d[t];

						int v=0;
						for (int h=j-1; h>p[j]; h--)//以下判断是否和j是同一父接点，自己在j-1项中不是服务机构的顶点需要转移
							if ((p[h]==p[j]) && (s[i-1][j-1][h]!=1))   v+=w[h];

					    t=p[p[j]];
						v+=w[p[j]];  //j父接点的权值
						
						int temp1=b[i-1][j-1]-lenth*v+w[j]*d[j];
						//fos<<temp1<<"     "<<lenth<<"     "<<v<<"     "<<b[i-1][j-1]<<endl;

						if ((b[i-1][j-1]<=temp)&&(b[i-1][j-1]<=temp1))
						{
							b[i][j]=b[i-1][j-1];
							for (int t=1; t<j; t++)  s[i][j][t]=s[i-1][j-1][t];
							s[i][j][j]=1;
						}
						else
						if ((temp1<temp)&&(temp1<b[i-1][j-1]))
						{
							for (int h=1; h<j; h++)  s[i][j][h]=s[i-1][j-1][h];
							s[i][j][p[j]]=1;
							b[i][j]=temp1;
						}
						else
							if ((temp<=temp1)&&(temp<b[i-1][j-1]))
							{
								for (int h=1; h<j; h++)  s[i][j][h]=s[i][j-1][h];
							    b[i][j]=temp;
							}
				}
				else  //p[j]是服务机构，不用考虑temp1情况			 
					{
						if (b[i-1][j-1]<=temp)
						{
							b[i][j]=b[i-1][j-1];
							for (int t=1; t<j; t++)  s[i][j][t]=s[i-1][j-1][t];
							s[i][j][j]=1;
						}
						else
						{
							b[i][j]=temp;
							for (int t=1; t<j; t++)  s[i][j][t]=s[i][j-1][t];
						}

					}
				/*for (int j=1; j<=n; j++)
						fos<<s[i][j][j]<<" ";
					fos<<endl;*/
			}
	    	else  
				b[i][j]=0;

	return b[k][n];
}

void main()
{

	ifstream fis;              // 定义输入文件
	//ofstream fos;              // 定义输出文件

	fis.open("input.txt");   //打开输入文件
	fos.open("output.txt");  //打开输出文件

// 处理输入
	int n,k;
	fis>>n>>k;

	int *w_old=new int[n+1];
	int *p_old=new int[n+1];
	int *d_old=new int[n+1];

	for (int i=1; i<=n; i++)    fis>>w_old[i]>>p_old[i]>>d_old[i];
	//for (i=1; i<=n;i++)  fos<<p[i]<<" ";
	//fos<<endl;

	int *w=new int[n+1];
	int *p=new int[n+1];
	int *d=new int[n+1];
	int *f=new int[n+1];

	//for (int i=1; i<=n; i++)    fis>>w[i]>>p[i]>>d[i];
	//for (i=1; i<=n; i++)    fos<<w[i]<<p[i]<<d[i]<<endl;
	
	int root=0, r=1, q=1;   //处理输入
	while (q<=n)
	{
		for (int i=1; i<=n; i++)
			if (p_old[i]==root)
			{
				d[r]=d_old[i];
				w[r]=w_old[i];
				p[r]=q-1;
				f[r]=i;
				r++;
			}
		root=f[q];
		q++;
	}

//	for (i=1; i<=n; i++)    fos<<w[i]<<p[i]<<d[i]<<endl;



// 处理输入k为0的情况
	if (k==0)
	{
		int *b=new int [n+1];
		
		b[1]=w[1]*d[1];
		
		for (int j=2; j<=n; j++)  
		{
			int len=0;
		    int m=j;
		    while (p[m]!=0)
			{
	      		len+=d[m];
		    	m=p[m];
			}
		    len+=d[m];
	     	b[j]=b[j-1]+len*w[j];
		}
		//fos<<b[n]<<endl;
		exit(1);
	}


// 处理输入n等于k的情况
	if (n==k)
	{
		fos<<0<<endl;
		exit(1);
	}

// 以下步骤用于建立一个标记服务机构的数组并初始化
	int ***s=new int * *[k+1];
    for(i=0; i<=k; i++)
	   s[i]=new int *[n+1];
    for( i=0;i<=k;i++)
	   for(int j=0;j<=n;j++)
	      s[i][j]=new int[n+1];
		
	//int **s=new int *[k+1];
	//for (int i=0; i<=k; i++)
	//	s[i]=new int[n+1];
	
	for (i=1; i<=k; i++)
		for (int j=1; j<=i; j++)
			s[i][i][j]=1;
	/*for (i=0; i<=k; i++)
		for (int j=i+1; j<=n; j++)
			s[i][i][j]=0;*/

	for (i=1;i<=n;i++)       //没有添加服务器的情况
		for (int j=1; j<=i; j++)
			s[0][i][j]=0;

	for (i=0; i<=k; i++)  
		for (int j=0;j<=n;j++)
			s[i][j][0]=1;

	/*for (i=0; i<=k; i++)
	{
		for (int j=1; j<=n; j++)
		{
			for (int p=1;p<=n;p++)
				fos<<s[i][j][p]<<" ";
			fos<<endl;
		}
		fos<<endl;
	}*/


// 调用函数
	fos<<thtree(n,k,w,p,d,s)<<endl;

//	for (i=1;i<=n;i++)
//		fos<<s[5][8][i]<<" ";

}