pku2724.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>
#include <string.h>
#define SIZE 1100

typedef struct Node
{
	int v[10];
	int n;
}Node;

Node G[SIZE];
int u[SIZE];
int v[SIZE];
char s[11];
int match[SIZE];
int N, M;

void init()
{
	memset(u, 0, sizeof(u));
	memset(G, 0, sizeof(G));
}

void Set_it()
{
	int v1 = 0, v2 = 0;
	int i;
	for (i = 0; i < N; i++)
	{
		v1 = v1 << 1;
		v2 = v2 << 1;
		if (s[i] == '1')
			v1 += 1, v2 += 1;
		if (s[i] == '*')
			v1 += 1;
	}
	u[v1] = 1;
	u[v2] = 1;
}

int DFS(int p)
{
	int i, t, id;
	for (i = 0; i < G[p].n; i++)
	{
		id = G[p].v[i];
		if (v[id] == 0)
		{
			t = match[id];
			match[id] = p;
			v[id] = 1;
			if (t == -1 || DFS(t))
				return 1;
			match[id] = t;
		}
	}
	return 0;
}

int Length(int x)
{
	int cnt, i;
	cnt = 0;
	for (i = 0; i < N; i++)
	{
		if ((1 << i) & x)
			cnt++;
	}
	return cnt;
}

void Solve()
{
	int i, j, cnt, tmp;
	init();
	for (i = 0; i < M; i++)
	{
		scanf("%s", s);
		Set_it();
	}
	M = 0;
	for (i = 0, M = 0; i < 1 << N; i++)
	{
		if (u[i])
			v[M++] = i;
	}
	for (i = 0; i < M; i++)
	{
		G[i].n = 0;
		for (j = 0; j < N; j++)
		{
			tmp = v[i] ^ (1 << j);
			if (u[tmp])
				G[i].v[G[i].n++] = tmp;
		}
	}
	cnt = 0;
	memset(match, -1, sizeof(match));
	for (i = 0; i < M; i++)
	{
		memset(v, 0, sizeof(v));
		cnt += DFS(i);
	}
	printf("%d\n", M - cnt / 2);
}

int main()
{
	while (EOF != scanf("%d %d", &N, &M) && (N || M))
		Solve();
	return 0;
}