1947.txt

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

#include <list>
#include <iostream.h>
using namespace std;
list< int > e[150];
int ans[150][151];
int n, p, answer;
int root;
int creat( int r )
{
	int i, j, n, m, c, temp[151];
	n = 1;
	ans[r][0] = 1;
	ans[r][1] = 0;
	list< int >::iterator iter;	
	for( iter = e[r].begin(); iter != e[r].end(); iter++ )
	{
		c = *iter;
		m = creat( c );
		for( i = 1; i<=n+m; i++ )
		{
			temp[i] = 99999;
			for( j = (i-n<0)?0:(i-n) ; j <= ( (i-1<m)?(i-1):m ) ; j++ )
			if( ans[c][j] + ans[r][i-j] < temp[i] )
			{
				temp[i] = ans[c][j] + ans[r][i-j];
			}
		}		
		for( i = 1; i<=n+m; i++ )
			ans[r][i] = temp[i];
		n += m;
	}
	if( ans[r][p] + (int) (r!=root) < answer ) answer = ans[r][p] + (int) (r!=root);
	return n ;
}
void init()
{
	int i, a, b, j;
	bool sign[150] = {0};
	scanf( "%d %d", &n, &p );
	for( i=0; i<n-1; i++ )
	{
		scanf( "%d %d", &a, &b );
		e[a-1].push_front( b-1 );
		sign[b-1] = true;
	}
	for( i=0; i<n; i++ )
	for( j=0; j<=n; j++ )
		ans[i][j] = 99999;
	answer = 99999;
	for( i=0; i<n; i++ )
	if( !sign[i] )
	{
		root = i;
		break;
	}
}
int main()
{
	init();
	creat(root);
	printf( "%d\n", answer );
	return 0;
}