题目描述 Description
给出一张n*n(n<=100)的国际象棋棋盘，其中被删除了一些点，问可以使用多少1*2的多米诺骨牌进行掩盖。
输入描述 Input Description
第一行为n，m（表示有m个删除的格子）
第二行到m+1行为x,y，分别表示删除格子所在的位置
x为第x行
y为第y列
输出描述 Output Description
一个数，即最大覆盖格数
样例输入 Sample Input
8 0
样例输出 Sample Output
32
数据范围及提示 Data Size & Hint
经典问题
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
二分图匹配~
覆盖一个点相当于是把两个点放入两个不同子集中，直接套匈牙利算法~
如果用bool变量记录连接状态会MLE，所以我用了邻接表来记，用匈牙利算法前先预处理出连接状态，输出结果的时候除以二就可以了~
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;int n,m,x,y,ans,c[101][101][2],val[3][5]={
{0,0,0,0,0},{0,1,-1,0,0},{0,0,0,1,-1}};
bool b[101][101];
vector<int> a[101][101][2];bool dfs(int u,int v)
{for(int i=0;i<a[u][v][0].size();i++)if(!b[a[u][v][0][i]][a[u][v][1][i]]){b[a[u][v][0][i]][a[u][v][1][i]]=1;if(!c[a[u][v][0][i]][a[u][v][1][i]][0] || dfs(c[a[u][v][0][i]][a[u][v][1][i]][0],c[a[u][v][0][i]][a[u][v][1][i]][1])){c[a[u][v][0][i]][a[u][v][1][i]][0]=u;c[a[u][v][0][i]][a[u][v][1][i]][1]=v;return 1;}}return 0;
}int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=m;i++) scanf("%d%d",&x,&y),b[x][y]=1;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(!b[i][j]){for(int k=1;k<=4;k++)if((i+val[1][k])>0 && (i+val[1][k])<=n && (j+val[2][k])>0 && (j+val[2][k])<=n && !b[i+val[1][k]][j+val[2][k]]){a[i][j][0].push_back(i+val[1][k]);a[i][j][1].push_back(j+val[2][k]);}}for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){memset(b,0,sizeof(b));if(dfs(i,j)) ans++;}printf("%d\n",ans/2);return 0;
}