【二分图+最大匹配+有难度】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: 
9625653panyanyany
2226
Accepted9168K125MSC++

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 MAXSIZE55*55

intr, c, xCnt, yCnt ;
intlink[MAXSIZE] ;
boolcover[MAXSIZE] ;
charmap[55][55] ;
boolgraph[MAXSIZE][MAXSIZE] ;
intmapx[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 ;
}