2486.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

 
#include <iostream>
#include <list>
#include <algorithm>
using namespace std;
int value[100];
int gone[100][201],m,K,n;
int back[100][201];
list<int> e[100];
void merge_back(int bk1[], int bk2[], int bk[], int maxstep )
{
	int i,j;
	for( i=0; i<=maxstep; i++ )
	{
		bk[i] = bk2[i];
		for( j=2; j<=i; j++ )
		if( bk1[j-2] + bk2[i-j] > bk[i] )
			bk[i] = bk1[j-2] + bk2[i-j];
	}
	
	return ;	
}	
void merge_gone(int go1[], int bk1[], int go2[], int bk2[], int go[], int maxstep )
{
	int i,j;
	for( i=0; i<=maxstep; i++ )
	{
		go[i] = go2[i];

		for( j=1; j<=i; j++ )
		if( go1[j-1] + bk2[i-j] > go[i] )
			go[i] = go1[j-1] + bk2[i-j];
		
		for( j=2; j<=i; j++ )
		if( bk1[j-2] + go2[i-j] > go[i] )
			go[i] = bk1[j-2] + go2[i-j];
	}

	return ;
}
int back_temp[201],gone_temp[201];
void calculate(int root,int maxstep,int father)
{
	int i,j;	
	list<int>::iterator iter;
	if( root>100 || root<0 )
		int *p = new int[10000000];	
	for( i=0; i<=maxstep ; i++ )
	{
		gone[root][i] = back[root][i] = value[root];
	}
	if( maxstep == 0 ) return ;
	for( iter = e[root].begin(); iter != e[root].end() ; iter++ )
	if( *iter != father )
	{
		calculate( *iter, maxstep-1 , root );
		merge_back( back[*iter], back[root], back_temp, maxstep );
		merge_gone( gone[*iter], back[*iter], gone[root], back[root], gone_temp,maxstep );
					
		copy( back_temp, back_temp+maxstep+1, back[root] );
		copy( gone_temp, gone_temp+maxstep+1, gone[root] );
	}

}
bool init()
{
	int i, a, b;
	cin>>n>>K;
	if( n>100 || K>200 )
		while(cout<<"faint");
	if( cin.fail() )return false;
	
	if( K > 2*n ) K = 2*n;	

	for( i=0; i<n; i++ )
	{
		cin >> value[i];
		e[i].clear();
	}	
	for( i=0; i<n-1; i++ )
	{
		cin >> a >> b;
		e[a-1].push_back( b-1 );
		e[b-1].push_back( a-1 );
	}	

	return true;
}
void doit()
{
	int answer = 0;	
	calculate( 0, K, -1); 	
	cout << gone[0][K] << endl;
}
int main()
{
	while( init() )
	{
		doit();
	}
	return 0;
}