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;
}
|