欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-04-18 13:14:16
...

 

/* 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 ;
}