1463.txt

来自「北大ACM题目例程 详细的解答过程 程序实现 算法分析」· 文本 代码 · 共 44 行

#include <stdio.h>
#include <memory.h>
#define min(a,b) ((a)<(b)?(a):(b))
int e[2000][20];
int en[2000];
int ans[2000][2], n;

void calc( int k, int f ) {
	int i;
	ans[k][0] = 0, ans[k][1] = 1;
	for( i=0; i<en[k]; i++ ) {
		if( e[k][i] != f ) {
			calc( e[k][i], k );
			ans[k][0] += ans[ e[k][i] ][1];
			ans[k][1] += min( ans[ e[k][i] ][0], ans[ e[k][i] ][1] );
		}
	}
}

int main( ) {
	int i, k, m, l, j;
	while( scanf( "%d", &n ) == 1 ) {

		memset( en, 0, sizeof en );

		for( j=0; j<n; j++ ) {
			scanf( "%d:(%d)", &k, &m );
			for( i=0; i<m; i++ ) {
				scanf( "%d", &l );
				e[k][ en[k]++ ] = l;
				e[l][ en[l]++ ] = k;
			}
		}

		calc( 0, -1 );
		printf( "%d\n", min( ans[0][0], ans[0][1] ) );
	}
	return 0;
}