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 22 #include 23 #include 24 #include 25 #include 26 #define M 5527 #define N 100028 using namespace std;29 vector 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 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
本文转自 小眼儿 博客园博客，原文链接：http://www.cnblogs.com/hujunzheng/p/3918485.html，如需转载请自行联系原作者