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

?

/* THE PROGRAM IS MADE BY PYY *//*----------------------------------------//Copyright (c) 2011 panyanyany All rights reserved.URL   : http://poj.org/problem?id=2226Name  : 2226 Muddy FieldsDate  : Sunday, December 04, 2011Time Stage : two hoursResult: 9625653panyanyany2226Accepted9168K125MSC++Test Data :Review :先附上大牛的解题报告，以示尊敬和感谢：http://blog.csdn.net/weiguang_123/article/details/6923711http://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*55intr, 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 ;}