/* 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 ;
}
分享到:
相关推荐
初期: 一.基本算法: (1)枚举. (poj1753,poj2965) (2)贪心(poj1328,poj2109,poj2586) ... (5)二分图的最大匹配 (匈牙利算法) (poj3041,poj3020) (6)最大流的增广路算法(KM算法). (poj1459,poj3436) ......
poj openjudge 1111题最大正向匹配 提交ac
POJ中级图算法所有题目【解题报告+AC代码】 我的所有POJ解题报告 http://blog.csdn.net/lyy289065406/article/details/6642573
各种搜索算法,配合POJ上的题目,含标程,及各题解题思路。
用递推方法+高精度算法,解决了poj1832 的连环锁问题,时间32ms。。。。。。
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
【二分图顶点覆盖->最小割->最大流->Dinic算法求解】 解题报告+AC代码 http://hi.csdn.net/!s/WKVPR0 ----> 我的所有POJ解题报告 http://blog.csdn.net/lyy289065406/article/details/6642573
NULL 博文链接:https://128kj.iteye.com/blog/1745671
北大POJ3009-Curling 2.0【DFS+Vector+回溯+剪枝】 解题报告+AC代码
POJ1048,加强版的约瑟夫问题 难度中等
北大POJ1159-Palindrome 解题报告+AC代码
北大POJ初级-图算法 解题报告+AC代码
北大POJ2187-Beauty Contest 解题报告+AC代码
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
北大POJ2002-Squares 解题报告+AC代码
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj分类poj分类poj分类poj分类
北大POJ2031-Building a Space Station【Prim+计算几何】 POJ2031-Building a Space Station【Prim+计算几何】
北大POJ1426-Find The Multiple【BFS+同余模】 解题报告+AC代码