2724.txt

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

Source

Problem Id:2724  User Id:fzk 
Memory:4020K  Time:265MS
Language:G++  Result:Accepted

Source 

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

#define null 0
const int size = 2010;
bool e[size][size];

int maxmatch( int n, int m, bool w[][size], int *p)
{

	int p_n[size];
	int p_m[size];

	bool sign[size];
	int q[size],from[size],s,t;

	int i,j,link,now,h;

	memset( p_n, -1, sizeof(int)*n );
	memset( p_m, -1, sizeof(int)*m );

	for(i=0;i<n;i++)
	if(p_n[i]==-1)
	{
		memset( sign, 0, sizeof(bool)*m );
                
		s=1;link=-1;
		from[0]=-1;

		q[0]=size-1;
		p_m[size-1]=i;

		for(t=0;t<s;t++)
		{
		   now=q[t];
		   for(j=0;j<m;j++)
		   {
			   if( w[p_m[now]][j] != null && sign[j]==0 )
			   {
					sign[j]=1;
					q[s]=j;
					from[s++]=t;

					if(p_m[j]==-1)
					{
						link=s-1;
						break;
					}
			   }
		   }
		   if(j<m)break;
		}

		if(t<s)
		{
			 while(from[link]!=-1)
			 {
					h=from[link];
					p_m[q[link]]=p_m[q[h]];
					p_n[p_m[q[h]]]=q[link];
					link=h;
			 }
		}

	}
	int an;

	for(i=0,an=0;i<n;i++)
	{
		if(p)p[i]=p_n[i];
		if(p_n[i]>=0)an++;
	}
	return an;
}

char s[2010][11];

int check( char *a, char *b ) {
	int i;
	for( i=0; a[i] && a[i] == b[i]; i++ )
		;
	if( !a[i] )
		return 2;
	for( i++; a[i] && a[i] == b[i]; i++ )
		;
	return !a[i];
}

int h;

void add( char *w, int key ) {
	int k;

	for( k=0; k<h; k++ )
		if( check( s[k], w ) == 2 )
			return;

	for( k=0; k<h; k++ )
		if( check( s[k], w ) ) {
			if( key )
				e[k][h] = 1;
			else
				e[h][k] = 1;
		}

	if( k == h )
		strcpy( s[h++], w );
}

int main() {
	int n, m, i, k, c;
	char *cp;
	char w[11];

	while( scanf("%d%d", &m, &n ) == 2 && n >0 && m > 0 ) {
		h = 0;
		memset( e, 0, sizeof e );

		for( i=0; i<n; i++ ) {
			scanf( "%s", w );

			c = 0;
			for( k=0; w[k]; k++ )
				if( w[k]=='1' )
					c++;

			cp = strchr( w, '*' );
			if( cp ) {
				*cp = '0';
				add( w, c%2 );
				*cp = '1';
				add( w, (c+1)%2 );
			}
			else {
				add( w, c%2 );
			}
		}
		printf( "%d\n", h-maxmatch( h, h, e, 0 ) );
	}
	return 0;
}