poj 2226 Muddy Fields(合理建图+二分匹配)

简介:
 1 /*
 2     题意:用木板盖住泥泞的地方,不能盖住草。木板任意长!可以重叠覆盖! '*'表示泥泞的地方,'.'表示草!
 3     思路:
 4          首先让我们回忆一下HDU 2119 Matrix这一道题,一个矩阵中只有0, 1,然后让我们通过选择一行,或者
 5          是一列将其所在行的或者所在列的 1全部删掉,求出最少需要几步?
 6          
 7          这道题的思路就是:将行标 和 列标值为1的建立一条边!通过匈牙利算法可以得到这个二分图的最大匹配数
 8          最大匹配数==最小顶点覆盖数!最小顶点覆盖就是用最少的点覆盖了这个二分图的所有的边,然后去掉这些
 9          最小覆盖中的顶点就可以去掉所有的边,也就是所有的 1都去掉了! 
10     
11     那么这道题该怎么办呢?其实和上面的思路差不多,只不过是不能在原图上解题!这道题每一行或者每一列
12     都有限制的因素,就是草地,覆盖泥泞的地方时不能覆盖草地,所以要想办法忽略草地的影响!
13     
14     解决方法:连通块的思路
如果一个连通区域的左右两侧无法延伸则为行连通块儿,上下无法延伸则为列连通块儿,把行连通块儿作为X集合,列连通块儿作为Y集合,则X与Y相连得到的边就代表所要覆盖的 泥泞区域。即可用匈牙利算法求出覆盖所有泥泞区域所需要的最少连通块儿。
1,现将每一行的不连在一起的泥泞土地赋给不同的编号(从1...cntR开始),也就是如果忽略
15 草地的话,泥泞的地方一共有cntR个行连通块! 16 2,同理每一列按照每一行的操作, 共有cntC个列连通块! 17 这样结题思路就和上面的那一道题一样了..... 18 19 g[i][j]=='*' 那么aR[i][j]就是该点新的行标, aC[i][j]就是该点行的列标 20 */ 21 #include<iostream> 22 #include<cstring> 23 #include<cstdio> 24 #include<algorithm> 25 #include<vector> 26 #define M 55 27 #define N 1000 28 using namespace std; 29 vector<int>v[N]; 30 char g[M][M]; 31 int vis[N]; 32 int linker[N]; 33 int aR[M][M], aC[M][M]; 34 int n, m; 35 36 bool dfs(int u){ 37 int len=v[u].size(); 38 for(int i=0; i<len; ++i){ 39 int vu=v[u][i]; 40 if(!vis[vu]) { 41 vis[vu]=1; 42 if(!linker[vu] || dfs(linker[vu])){ 43 linker[vu]=u; 44 return true; 45 } 46 } 47 } 48 return false; 49 } 50 51 int main(){ 52 while(scanf("%d%d", &n, &m)!=EOF){ 53 int cntR=1, cntC=1; 54 for(int i=1; i<=n; ++i) 55 scanf("%s", g[i]+1); 56 for(int i=1; i<=n; ++i) 57 for(int j=1; j<=m; ++j) 58 if(g[i][j]=='*'){ 59 aR[i][j]=cntR; 60 if(j+1>m || g[i][j+1]!='*') 61 ++cntR; 62 } 63 for(int j=1; j<=m; ++j) 64 for(int i=1; i<=n; ++i) 65 if(g[i][j]=='*'){ 66 aC[i][j]=cntC; 67 if(i+1>n || g[i+1][j]!='*') 68 ++cntC; 69 } 70 for(int i=1; i<=n; ++i) 71 for(int j=1; j<=m; ++j) 72 if(g[i][j]=='*') 73 v[aR[i][j]].push_back(aC[i][j]); 74 75 int ans=0; 76 memset(linker, 0, sizeof(linker)); 77 for(int i=1; i<cntR; ++i){ 78 memset(vis, 0, sizeof(vis)); 79 if(dfs(i)) ++ans; 80 } 81 printf("%d\n", ans); 82 for(int i=1; i<cntR; ++i) 83 v[i].clear(); 84 } 85 return 0; 86 }
复制代码









本文转自 小眼儿 博客园博客,原文链接:http://www.cnblogs.com/hujunzheng/p/3918485.html,如需转载请自行联系原作者
目录
相关文章
|
Java
poj 1205 :Water Treatment Plants (DP+高精度)
思路:DP+高精度。DP部分,易得最右边城市的状态只可能用3种:>V, V, <。故分三种状态讨论,设dp[i][0]为第i个城市的状态为:> V ,dp[i][1]为:V ,dp[i][2]为:<。由实际流动的可能性可以得到状态转移方程:
45 0
poj 2362 hdoj 1518 Square(搜索)
不难了解,小棒子的长度越长,其灵活性越差。例如长度为5的一根棒子的组合方式要比5根长度为1的棒子的组合方式少,这就是灵活性的体现。
54 0
|
网络架构
POJ 3250 Bad Hair Day、POJ 2796 Feel Good(单调栈)
POJ 3250 Bad Hair Day、POJ 2796 Feel Good(单调栈)
[UVA1364 | POJ | NC]Knights of the Round Table | Tarjan 求点双 | 二分图 | 综合图论
我们可以很轻松地发现,被提出的都是在点双连通分量之外的,比如该图中的1 和 5 ,那么怎么判断哪些点不在环中呢? 此时我们还可以逆向思考,不 在 环 中 的 = = 总 的 − 在 环 中 的,所以说现在问题就转换成了满足条件的环内的点的个数
133 0
[UVA1364 | POJ | NC]Knights of the Round Table | Tarjan 求点双 | 二分图 | 综合图论