1909.txt

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

#include <stdio.h>
#include <memory.h>
#define abs(a) (((a)>0)?(a):(-a))

int ans[10000];
short need[10000], n, box[10000];
short begin[10000],end[10000], degree[10000];
short to[20010];

bool init()
{
	short i, v, d, s, t;

	scanf( "%d", &n );

	if( n == 0 ) return false;

	memset(ans, 0, n*sizeof(int));
	memset(degree, 0, n*sizeof(short));	

	for(s=0,i=0; i<n; i++)
	{
		scanf( "%hd", &v);
		v--;
		scanf( "%hd%hd", &box[v],&d);
		
		begin[v] = s;
		while( d-- )
		{
			scanf( "%hd", &t );
			to[s] = t-1;
			degree[ t-1 ]++;
			s++;
		}
		end[v] = s;
	}

	return true;
}

void calc(int v)
{
	int i,k;

	need[v] = 1 - box[v] ;	
	
	for( i = begin[v]; i < end[v]; i++)
	{
		k=to[i];
	
		calc( k );
		ans[v] += abs( need[k] ) + ans[k];
		need[v] += need[k];
	}
}

int main()
{
	int i;

	while( init() )
	{
		for( i=0; i<n; i++ )
		if( !degree[i] )
		{
			calc(i);
			printf("%d\n",ans[i]);
			break;
		}
	}

	return 0;
}