【二分图+最大匹配】北大 poj 2724 Purifying Machine

 

/* THE PROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//
	Copyright (c) 2011 panyanyany All rights reserved.

	URL   : http://poj.org/problem?id=2724
	Name  : 2724 Purifying Machine

	Date  : Monday, December 19, 2011
	Time Stage : one and half hour

	Result: 
9671768	panyanyany
2724
Accepted	4104K	391MS	C++
2105B	2011-12-19 22:18:09

Test Data :

Review :
凡是涉及字符串处理的，肯定会出错……这题也逃不了这个怪圈。
一开始的时候不知道怎么判断是否只差一位，然后就找解题报告，
终于发现了一个巧妙的方法，感觉跟树状数组的 lowbit 差不多……
具体的分析请点击下列大牛的地址：
AekdyCoin的空间 		http://hi.baidu.com/aekdycoin/blog/item/2dac891ea09ef9f2e1fe0b67.html
Uriel's Corner 			http://www.cppblog.com/Uriel/articles/122014.html
nizhenyang的博客 		http://blog.sina.com.cn/s/blog_6a98ae6c0100nflu.html
月拌西凉的空间 		http://hi.baidu.com/%D4%C2%B0%E8%CE%F7%C1%B9/blog/item/6eb3893752e50f4ead4b5ff2.html
//----------------------------------------------------------------------------*/

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

#define MAXSIZE	2002

int		n, m, cnt ;
int		seq[MAXSIZE], link[MAXSIZE] ;
bool	cover[MAXSIZE] ;
bool	graph[MAXSIZE][MAXSIZE] ;

void cnvToDig (char *str, int *a, int *b)
{
	int i, starPos ;
	*a = *b = 0 ;
	starPos = -1 ;
	for (i = 0 ; i < strlen (str) ; ++i)
	{
		if (str[i] == '*')
		{
			starPos = (n - i - 1) ;
		}
		else if (str[i] == '1')
		{
			*a |= 1 << (n - i - 1) ;
		}
	}

	*b = (starPos == -1) ? (*a) : (*a | (1 << starPos)) ;
}

inline bool onlyDiff (int lhs, int rhs)
{
	int c = lhs ^ rhs ;
	return c && !(c & (c-1)) ;
}

bool noRepeat (int a)
{
	int i ;
	for (i = 0 ; i < cnt ; ++i)
		if (seq[i] == a)
			return false ;
	return true ;
}

bool find (int cur)
{
	int i, j ;
	for (i = 0 ; i < cnt ; ++i)
	{
		if (!cover[i] && graph[cur][i])
		{
			cover[i] = true ;
			if (link[i] == -1 || find (link[i]))
			{
				link[i] = cur ;
				return true ;
			}
		}
	}
	return false ;
}

int main ()
{
	int		i, j ;
	int		a, b ;
	int		sum ;
	char	str[20] ;
	while (scanf ("%d%d", &n, &m), n | m)
	{
		getchar () ;
		for (i = cnt = 0 ; i < m ; ++i)
		{
			gets (str) ;
			cnvToDig (str, &a, &b) ;
//			printf ("%d, %d\n",a , b) ;

			if (noRepeat(a))
				seq[cnt++] = a ;

			if (a != b && noRepeat (b))
				seq[cnt++] = b ;
		}

		memset (graph, false, sizeof (graph)) ;
		for (i = 0 ; i < cnt ; ++i)
			for (j = i + 1 ; j < cnt ; ++j)
				if (onlyDiff(seq[i], seq[j]))
					graph[i][j] = graph[j][i] = true ;
				
		sum = 0 ;
		memset (link, -1, sizeof (link)) ;
		for (i = 0 ; i < cnt ; ++i)
		{
			memset (cover, 0, sizeof (cover)) ;
			sum += find (i) ;
		}
		printf ("%d\n", cnt - sum / 2) ;
	}
	return 0 ;
}