【二分图+最大匹配+有难度】poj 2226 Muddy Fields

 

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

	URL   : http://poj.org/problem?id=2226
	Name  : 2226 Muddy Fields

	Date  : Sunday, December 04, 2011
	Time Stage : two hours

	Result: 
9625653	panyanyany
2226
Accepted	9168K	125MS	C++

Test Data :

Review :
先附上大牛的解题报告，以示尊敬和感谢：
http://blog.csdn.net/weiguang_123/article/details/6923711
http://blog.csdn.net/acmj1991/article/details/6825090

这题比较纠结，虽然跟 poj 3041 Asteroids 有点像，但毕竟还是很不相同的。
起码一开始没有思路，看了人家的解题报告，也是琢磨了好久的。

具体思路：
	因为这是一个矩阵，那么就有两种方法可以适用于任何情况。第一种是把矩阵划分为
r 行，然后按行来铺木板，这样不论有多少人泥地，怎么分布，都可以铺上去。第二种是把
矩阵划分为 c 列，然后按列来铺木板。
	这两种方法的特点是不考虑最优化。

	如果要考虑最优化呢？可以把按行划分的所有木板编号，为 Y 点集，把按列划分的
所有木板编号，为 X 点集。
	那么，怎么样使 x 和 y 点集连线呢？可以先对被同一块木板覆盖的方格都统一编号
为木板的编号。不过，同一个方格必然会被两个不同的木板覆盖，所以就要有两套图，
第一套只记录以行划分的编号，第二套只记录以列划分的编号。如此一来，同一点的两个
不同编号（比如x1, y1)，就代表 X 点集中 点x1 与 Y 点集中 点y1 有一条公共边。
	然后再二分匹配求最大匹配即可。

	最后，要注意数组，不能开太大，否则MLE，太小了则WA
//----------------------------------------------------------------------------*/

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

#define MAXSIZE		55*55

int		r, c, xCnt, yCnt ;
int		link[MAXSIZE] ;
bool	cover[MAXSIZE] ;
char	map[55][55] ;
bool	graph[MAXSIZE][MAXSIZE] ;
int		mapx[55][55], mapy[55][55] ;

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

int getSum ()
{
	int i ;
	int sum ;
	sum = 0 ;

	memset (link, 0, sizeof (link)) ;
	for (i = 1 ; i <= yCnt ; ++i)
	{
		memset (cover, 0, sizeof (cover)) ;
		sum += find (i) ;
	}
	return sum ;
}

int main ()
{
	int i, j ;

	while (~scanf ("%d%d", &r, &c))
	{
		for (i = 0 ; i < r ; ++i)
			scanf ("%s", map[i]) ;

		memset (mapx, 0, sizeof (mapx)) ;
		memset (mapy, 0, sizeof (mapy)) ;
		yCnt = 0 ;
		for (i = 0 ; i < r ; ++i)
			for (j = 0 ; j < c ; ++j)
				if (map[i][j] == '*')
				{
					++yCnt ;
					while (j < c && map[i][j] == '*')
					{
						mapy[i][j] = yCnt ;
						++j ;
					}
				}
		xCnt = 0 ;
		for (j = 0 ; j < c ; ++j)
			for (i = 0 ; i < r ; ++i)
				if (map[i][j] == '*')
				{
					++xCnt ;
					while (i < r && map[i][j] == '*')
					{
						mapx[i][j] = xCnt ;
						++i ;
					}
				}

		memset (graph, 0, sizeof (graph)) ;
		for (i = 0 ; i < r ; ++i)
			for (j = 0 ; j < c ; ++j)
				graph[mapy[i][j]][mapx[i][j]] = 1 ;

		printf ("%d\n", getSum ()) ;
	}
	return 0 ;
}