POJ2226二分图最小覆盖问题

考虑一个尺寸为n×m的网格，其中某些单元格含有泥泞，而其他则保持清洁。任务是利用宽度恒定为1、长度不限的木板完全覆盖所有的泥泞区域，同时确保这些木板不会触及任何清洁区域，木板间可以相互重叠。给定条件为n, m ≤ 50。

解决问题的关键在于理解每个泥泞单元格可以由横向或纵向放置的木板覆盖。具体来说，横向木板用于覆盖同一行内连续的泥泞单元格（称为行泥泞段），而纵向木板则覆盖同一列内的连续泥泞单元格（称为列泥泞段）。

接下来，将所有行泥泞段视为二分图的左侧节点集，所有列泥泞段视为右侧节点集。对于每一个泥泞单元格，从其所属的行泥泞段向列泥泞段绘制一条边。最终，所求即为该二分图的最小顶点覆盖数。

值得注意的是，此问题与棋盘上的车辆布局问题存在本质区别，后者不适合采用行列直接建图的方法。正确的方法是以横向木板作为左侧图形，纵向木板作为右侧图形进行建模。

以下是实现这一算法的C++代码示例：
```cpp
#include
#include
#include
using namespace std;
const int N = 55;
const int M = N * N;
char a[N][N];
int row[N][N], col[N][N];
int R, C;
bool vis[M];
int linker[M];
int to[M], nxt[M];
int head[M], tot;
int n, m;

void addedge(int u, int v) {
++tot;
to[tot] = v;
nxt[tot] = head[u];
head[u] = tot;
}

bool dfs(int u) {
for (int i = head[u]; ~i; i = nxt[i]) {
int v = to[i];
if (!vis[v]) {
vis[v] = 1;
if (linker[v] == -1 || dfs(linker[v])) {
linker[v] = u;
return 1;
}
}
}
return 0;
}

int hungary() {
int ret = 0;
memset(linker, -1, sizeof(linker));
for (int i = 1; i <= R; ++i) {
memset(vis, 0, sizeof(vis));
if (dfs(i)) ++ret;
}
return ret;
}

int main() {
while (~scanf("%d %d", &n, &m)) {
memset(row, 0, sizeof(row));
memset(col, 0, sizeof(col));
memset(head, -1, sizeof(head));
tot = -1;
R = C = 0;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) {
cin >> a[i][j];
if (a[i][j] == '*') {
if (row[i][j - 1]) row[i][j] = row[i][j - 1];
else row[i][j] = ++R;
if (col[i - 1][j]) col[i][j] = col[i - 1][j];
else col[i][j] = ++C;
}
}
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
if (a[i][j] == '*') addedge(row[i][j], col[i][j]);
printf("%d\n", hungary());
}
return 0;
}
```
来源：https://www.cnblogs.com/bxd123/p/10932872.html