POJ 3041 (问题1) 给出一个N*N的矩阵，有些格子上有障碍，要求每次消除一行或者一列的障碍，最少消除多少次可以全部清除障碍。
POJ 2226 (问题2) 给出的是N*M的矩阵，同样是有障碍的格子，要求每次只能消除一行或一列中相邻的格子，最少消除多少次可以全部清除。
对于问题1，可以考虑把每行x或者每列y看成一个点，而障碍物(x,y)可以看做连接x和y的边。按照这种思路构图后。问题就转化成为选择最少的一些点(x或y)，使得从这些点与所有的边相邻，其实这就是最小点覆盖问题。在二分图中，最小点覆盖数=最大匹配数。所以可以用匈牙利算法解决。
对于问题2，不能一次消除一行或一列，只能一次消除相邻的，怎么办？
实质上问题2和问题1是相同的，只是需要一步预处理。扫描一遍输入的矩阵，把每行和每列中相邻的障碍物看成一个点，记录一下，然后加边。这样就转化成了问题1。
  POJ 3041
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define maxn 501
int match[maxn];
int map[maxn][maxn];
bool v[maxn];
int n,m;
bool dfs(int p)
{
int i;
for(i=1;i<=n;i++)
{
if(map[p][i]&&!v[i])
{
v[i]=1;
if(match[i]==-1||dfs(match[i]))
{
match[i]=p;
return 1;
}
}
}
return 0;
}
int Hungry()
{
int i;
int ans=0;
for(i=1;i<=n;i++)
{
memset(v,0,sizeof(v));
if(dfs(i))
ans++;
}
return ans;
}
int main()
{
int i,j,k;
scanf("%d%d",&n,&k);
for(m=1;m<=k;m++)
{
scanf("%d%d",&i,&j);
map[i][j]=1;
}
memset(match,-1,sizeof(match));
printf("%d\n",Hungry());
}
POJ 2226
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define maxn 900
int match[maxn];
int map[maxn][maxn];
char s[52][52];
int cx[52][52];
int cy[52][52];
bool v[maxn];
int n,m;
int nx,ny;//x的数目和y的数目
bool dfs(int p)
{
int i;
for(i=1;i<=ny;i++)
{
if(map[p][i]&&!v[i])
{
v[i]=1;
if(match[i]==-1||dfs(match[i]))
{
match[i]=p;
return 1;
}
}
}
return 0;
}
int Hungry()
{
int i;
int ans=0;
for(i=1;i<=nx;i++)
{
memset(v,0,sizeof(v));
if(dfs(i))
ans++;
}
return ans;
}
int main()
{
int i,j,k;
scanf("%d%d",&n,&m);
getchar();
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
s[i][j]=getchar();
}
getchar();
}
nx=0;
ny=0;
for(i=1;i<=n;i++)
{
j=1;
while(j<=m)
{
if(s[i][j]=='*')
{
nx++;
while(s[i][j]=='*')
{
cx[i][j]=nx;
j++;
}
}
else j++;
}
}
for(j=1;j<=m;j++)
{
i=1;
while(i<=n)
{
if(s[i][j]=='*')
{
ny++;
while(s[i][j]=='*')
{
cy[i][j]=ny;
i++;
}
}
else i++;
}
}
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
if(s[i][j]=='*')
{
map[cx[i][j]][cy[i][j]]=1;
}
}
}
memset(match,-1,sizeof(match));
printf("%d\n",Hungry());
return 0;
}
|