2724.cpp

ACM北京赛区比赛的试题源码,在PKU在线评测可以通过.

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

char v[1024];
int N,M;
int match[1024];
int a[1024][10];
int na[1024];
int m[11] = {1,2,4,8,16,32,64,128,256,512,1024};

int FindPath(int node)
{
	int fr[1024];
	int q[1024];
	int f,l,i,j,t;
	f = l = 0;
	q[0] = node;
	memset(fr,0xff,sizeof fr);
	while (f<=l)
	{
		for(i = 0;i<na[q[f]];i++) if (fr[a[q[f]][i]] == -1)
		{
			if (match[a[q[f]][i]] != -1)//matched
			{
				l ++;
				q[l] = match[a[q[f]][i]];
				fr[a[q[f]][i]] = q[f];
			}
			else 
			{
				j = q[f];
				i = a[q[f]][i];
				while (1)
				{
					t = match[j];
					match[j] = i;
					match[i] = j;
					if (t == -1) break;
					i = t;
					j = fr[t];	
				}
				return 1;
			}
		}
		f++;
	}
	return 0;
}


int MaxMatch()
{
	memset(match,0xff,sizeof match);
	int ret = 0;
	for(int i=0;i<m[N];i++) if (v[i] && match[i] == -1) ret += FindPath(i);
	return ret;
}

int main()
{
	int i,j;
	int num1,num2;
	int all;
	bool type;
	char str[10];
	char ch;
	scanf("%d %d",&N,&M);
	while (N)
	{
		memset(v,0,sizeof v);
		for(i=0;i<M;i++)
		{
			num1 = num2 = 0;
			type = false;
			scanf("%s",str);
			for(j=0;j<N;j++)
			{
				ch = str[j];
				if (ch == '*') 
				{
					type = true;
					num1 += m[N-1-j];
					continue;
				}
				num1 += m[N-1-j]*(ch-'0');
				num2 += m[N-1-j]*(ch-'0');
			}
			if (type)
			{
				v[num1] = 1;
				v[num2] = 1;
			} else v[num1] = 1;
		}
		//got all numbers
		memset(na,0,sizeof na);
		all = 0;
		for(i=0;i<m[N];i++) if (v[i])
		{
			all++;
			for(j=0;j<N;j++) if (v[i^m[j]])
			{
				a[i][na[i]] = i^m[j];
				na[i]++;
			}
		}
		int n = MaxMatch();
		printf("%d\n",all-n);
		scanf("%d %d",&N,&M);
	}
	return 0;
}