P1035
时间限制: 1 Sec 内存限制: 128 MB
提交: 87 解决: 36
[提交][状态][讨论版]
题目描述
给出一张n*n(n< =100)的国际象棋棋盘，其中被删除了一些点，问可以使用多少1*2的多米诺骨牌进行掩盖。
输入
第一行为n，m（表示有m个删除的格子） 第二行到m+1行为x,y，分别表示删除格子所在的位置 x为第x行 y为第y列
输出
一个数，即最大覆盖格数
样例输入
8 0
样例输出
32
提示
经典问题
建图，比较简单，一般人都想得到，所以一个点与其上下左右的点连边，然后就可以了，求一次二分图最大匹配。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std; const int x[]={,,,-},y[]={-,,,}; int n,m;
bool map[][],flag[];
int head[],cnt,next[],rea[];
int fa[];
void add(int u,int v)
{
cnt++;
next[cnt]=head[u];
head[u]=cnt;
rea[cnt]=v;
}
bool dfs(int u)
{
for(int i=head[u];i!=-;i=next[i])
{
int v=rea[i];
if(flag[v]==false)
{
flag[v]=;
if(fa[v]==-||dfs(fa[v]))
{
fa[v]=u;
return true;
}
}
}
return false;
}
int solve()
{
int num=;
memset(fa,-,sizeof(fa));
for(int i=;i<=n*n;i++)
{
memset(flag,false,sizeof(flag));
num+=dfs(i);
}
return num;
}
int main()
{
cnt=;
memset(head,-,sizeof(head));
memset(map,false,sizeof(map));
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
map[x][y]=true;
}
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
if(!map[i][j])
{
int numx=(i-)*n+j;
for(int k=;k<;k++)
{
int xx=i+x[k],yy=j+y[k];
if(xx>=&&xx<=n&&yy>=&&yy<=n&&!map[xx][yy])
{
int numy=(xx-)*n+yy;
add(numx,numy);
}
}
}
printf("%d\n",solve()/);
}