2114.txt

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

#include <vector>
#include <stdio.h>
#include <algorithm>
using namespace std;
typedef pair< int, int > edge;
vector< edge > e[10010];
int v[10010],s[10010];
int st[10010],sn;
bool sign[10010];
int n;
int find_root_search( int r, int f )
{
	int temp,i,j;
	v[r] = 0;
	s[r] = 1;
	st[sn++] = r;
	for( i=0; i<e[r].size(); i++ )
	{
		j = e[r][i].first;
	
		if( j != f && sign[j] )
		{
			temp = find_root_search( j , r );
			if( temp > v[r] ) v[r] = temp;
			s[r] += temp;
		}
	}

	return s[r];
}
int find_root( int r, int f )
{
	int i,h,j,t;
	
	sn = 0;
	h = find_root_search( r, f );

	r = st[0];
	for( i=0; i<sn; i++ )
	{
		j = st[i];
		if( ( t = h - s[j] ) > v[j] ) v[j] = t;
		if( v[j] < v[r] ) r = j;
	}

	return r;
}
int _dis[100],mm;
int dis[100],m;
int id[100];
int ans[10010],*temp=st,ans_n;
bool ok[100];
int cn;
void calc_dis( int r, int len, int f )
{
	int i, j;
	ans[cn++] = len;	
	for( i=0; i<e[r].size(); i++ )
	{
		j = e[r][i].first;	
		if( j != f && sign[j] )
		{
			calc_dis( j, len + e[r][i].second, r );
		}
	}
}
void search( int r, int num, int f, int len )
{
	int i,j,h,a,num1,rr=r,t;
	int *p1,*p2,*q1,*q2,*p;
	ans[ans_n++] = 0;
	sn = 0;
	r = find_root( r, f );
	sign[r] = false;
	for( i=0; i<e[r].size(); i++ )
	if( sign[ j = e[r][i].first ] )
	{
		h = e[r][i].second;
		num1 = ans_n;
		search( j, num1, r, h );
		if( m == 0 )
			return;
		p1 = ans + num; q1 = ans + num1;
		p2 = ans + num1; q2 = ans + ans_n;
		if( q1-p1 > q2-p2 )
		{
			swap( p1, p2 );
			swap( q1, q2 );
		}
		for( p=p1; p<q1; p++ )
		{
			for( a=0; a<m; a++ )
			{
				t = dis[a]-*p;
				if( t >= *p2 && t<=*(q2-1) && binary_search( p2, q2, t ) )
				{
					ok[ id[a] ] = true;
					dis[a] = dis[m-1];
					id[a] = id[m-1];
					m--;
					a--;
				}
			}
		}
		merge( p1, q1, p2, q2, temp );
		copy( temp, temp+ans_n-num, ans+num );
	}
	sign[r] = true;
	cn = num;
	calc_dis( rr, len, f );
	sort( ans+num, ans+ans_n );
}
bool init()
{
	int i,d,c;
	scanf( "%d", &n );
	if( n == 0 )return false;
	for( i=0; i<n; i++ )
	{
		e[i].clear();
		sign[i] = true;
	}
	for( i=0; i<n; i++ )
	while( 1 )
	{
		scanf( "%d", &d );
		if( d == 0 ) break;
		scanf( "%d", &c );
		e[i].push_back( edge( d-1, c ) );
		e[d-1].push_back( edge( i, c ) );
	}
	m = 0;
	while( 1 )
	{
		scanf( "%d", &dis[m] );
		if( dis[m] == 0 )break;
		
		_dis[m] = dis[m];
		id[m] = m;
		ok[m] = false;
		m++;
	}
	mm = m;
	ans_n = 0;
	return true;

}
int main()
{
	int i;

	while( init() )
	{
		search( 0, 0, -1, 0 );

		for( i=0; i<mm; i++ )
		{
			if( ok[i] )	printf( "AYE\n" );
			else printf( "NAY\n" );
		}
		printf( ".\n" );
	}
	return 0;
}