1719.txt

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

 

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

int e[1000][1000], en[1000], col[1000];
int match[1000];

bool sign1[1000], sign2[1000];
int flag[1000];

bool search( int a )
{
	int i, j;

	sign1[a] = true;

	for( i=0; i<en[a]; i++ )
	{
		j = e[a][i];
		if( !sign2[j] )
		{
			sign2[j] = true;
			if( match[j] == -1 || ( !sign1[match[j]] && search( match[j] ) ) )
			{
				match[j] = a;
				flag[a] = j;
				return true;
			}
		}
	}

	return false;
}

int main( )
{
	int cas, i, c, r, a, b;

	scanf( "%d", &cas );

	while( cas-- )
	{
		scanf( "%d%d", &r, &c );

		for( i=0; i<r; i++ )
			en[i] = 0;

		for( i=0; i<c; i++ )
		{
			scanf( "%d %d", &a, &b );
			col[i] = a;
			a--, b--;
			e[a][en[a]++] = i;
			e[b][en[b]++] = i;
		}

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

		for( i=0; i<r; i++ )
		if( flag[i] == -1 )
		{
			memset( sign1, 0, sizeof sign1 );
			memset( sign2, 0, sizeof sign2 );
			if( !search( i ) )
				break;
		}
		
		if( i < r )
			printf( "NO\n" );
		else
		{
			for( i=0; i<c; i++ )
			{
				if( match[i] != -1 )
					printf( "%d", match[i]+1 );
				else 
					printf( "%d", col[i] );

				if( i < c-1 )printf( " " );
				else printf( "\n" );
			}
		}
	}

	return 0;
}