1469.txt

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

#include <stdio.h>
#include <memory.h>

bool e[100][300];
int match[300], n;

bool sign1[100];
bool flag[100];

bool search( int a )
{
	int i;

	if( sign1[a] )
		return false;

	sign1[a] = true;

	for( i=0; i<n; i++ )
	if( e[a][i] )
	{
		if( match[i] == -1 ||  search( match[i] ) )
		{
			match[i] = a;
			flag[a] = true;
			return true;
		}
	}

	return false;
}

int main( )
{
	int cas, p, i, j, m;

	scanf( "%d", &cas );

	while( cas-- )
	{
		scanf( "%d%d", &p, &n );
		memset( e, 0, sizeof e );

		for( i=0; i<p; i++ )
		{
			scanf( "%d", &m );
			while( m-- )
			{
				scanf( "%d", &j );
				e[i][j-1] = true;
			}
		}

		memset( flag, 0, sizeof flag );
		memset( match, -1, sizeof match );

		for( i=0; i<p; i++ )
		if( !flag[i] )
		{
			memset( sign1, 0, sizeof sign1 );
			if( !search( i ) )
				break;
		}

		if( i < p )
			printf( "NO\n" );
		else
			printf( "YES\n" );
	}

	return 0;
}