AcWing 377. 泥泞的区域(最小点覆盖)
原题链接
中等
作者:
小小_88
,
2022-04-28 16:48:37
,
所有人可见
,
阅读 364
泥泞的区域
C++ 代码
/*
对于每块泥块都需要被横向或竖向的木板至少覆盖一次。
由于木板不能盖住干净的地面,所以横着的木板只能覆盖同一行若干个连续的泥块。
竖着的木板只能覆盖同一列若干个连续的泥块。我们把这些连续的泥块分别分成 行泥块 和 列泥块。
对于每个泥块,把它所在的行泥块和列泥块之间连一条边。
那么可以发现,行泥块就是左部节点,列泥块就是右部节点。我们只需要保证每条边至少有一个节点被覆盖即可。
因此求的就是二分图的最小点覆盖,等价于求最大匹配数,用匈牙利算法来解决。
*/
#include <iostream>
#include <cstring>
using namespace std;
const int N = 55;
int n, m;
char g[N][N]; //地图
bool used[N][N]; //记录每个点是否被访问过
int rcnt, ccnt; //记录行泥块和列泥块的数量
int rid[N][N], cid[N][N]; //记录每个点所属的行泥块和列泥块
bool w[N * N][N * N]; //w[i][j] 记录第i个行泥块和第j个列泥块是否存在边
bool st[N * N];
int match[N * N];
bool find(int u) //为第u个行泥块匹配对应的列泥块
{
for(int i = 1; i <= ccnt; i++)
if(w[u][i] && !st[i])
{
st[i] = true;
if(!match[i] || find(match[i]))
{
match[i] = u;
return true; //匹配成功
}
}
return false; //匹配失败
}
int main()
{
scanf("%d%d", &n, &m);
for(int i = 0; i < n; i++) scanf("%s", g[i]);
for(int i = 0; i < n; i++) //枚举每一个位置
for(int j = 0; j < m; j++)
if(g[i][j] == '*' && !used[i][j]) //如果发现一个未搜索过的泥块,说明发现一个新的行泥块
{
rcnt++; //行泥块数量+1
int k = j;
while(k < m && g[i][k] == '*') //找出整个行泥块
{
used[i][k] = true; //标记所有找到的泥块
rid[i][k] = rcnt; //标记所有泥块属于哪个行泥块
k++;
}
}
memset(used, 0, sizeof used); //重置标记
for(int i = 0; i < n; i++) //枚举每一个位置
for(int j = 0; j < m; j++)
if(g[i][j] == '*' && !used[i][j]) //如果发现一个未搜索过的泥块,说明发现一个新的列泥块
{
ccnt++; //列泥块数量+1
int k = i;
while(k < n && g[k][j] == '*') //找出整个列泥块
{
used[k][j] = true; //标记所有找到的泥块
cid[k][j] = ccnt; //标记所有泥块属于哪个列泥块
k++;
}
}
//建图
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
if(g[i][j] == '*') //对于每个泥块,将它属于的行泥块和列泥块之间连一条边
w[rid[i][j]][cid[i][j]] = true;
int res = 0; //记录最大匹配数
for(int i = 1; i <= rcnt; i++) //枚举左部节点
{
memset(st, 0, sizeof st); //重置标记
if(find(i)) res++; //如果匹配成功,最大匹配数+1
}
printf("%d\n", res);
return 0;
}