poj2226 二分图经典建图求最小点覆盖
题意::给出一个N行M列的图,’*’代表稀泥,’.’代表草地,现在要用一些木板把所有的稀泥盖住,但是不能盖住草地。一张木板只能盖住一行或者一列中的一部分,求至少要用多少木板把所有的稀泥盖住。
把横向连续的点压在一起作为L,把列向连续的点压在一起作为R,如果两者有交集,就从L到R连一条边。求最小点覆盖(==最大匹配数)
#include <cstdio>
#include <cstring>
#include <iostream>
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;
}
版权声明:本文为jay__bryant原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。