2986 - 棋盘覆盖
给出一张nn(n<=100)的国际象棋棋盘，其中被删除了一些点，问可以使用多少12的多米诺骨牌进行掩盖。
Input
第一行为n，m（表示有m个删除的格子）
第二行到m+1行为x,y，分别表示删除格子所在的位置
x为第x行
y为第y列
Output
一个数，即最大覆盖格数
Examples
Input
8 0
Output
32
Solution C++
#include<iostream> using namespace std; int n,m,ans(0),a[5005][10],match[5005],x=0,y=0,num[10005]; bool used[5005],can[10005]; void init() { cin>>n>>m; fill(can,can+10005,1); for (int i=1,b,c;i<=m;i++) { cin>>b>>c; can[(b-1)*n+c]=false; } for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) if ((i+j)%2==0&&can[(i-1)*n+j]) num[(i-1)*n+j]=(++y); for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) { if ((i+j)%2==1&&can[(i-1)*n+j]) { a[++x][0]=0; if (can[(i-1)*n+j-1]&&j-1>0) a[x][++a[x][0]]=num[(i-1)*n+j-1]; if (can[(i-1)*n+j+1]&&j+1<=n) a[x][++a[x][0]]=num[(i-1)*n+j+1]; if (can[(i-2)*n+j]&&i-2>=0) a[x][++a[x][0]]=num[(i-2)*n+j]; if (can[(i)*n+j]&&i<n) a[x][++a[x][0]]=num[(i)*n+j]; } } } bool cross(int k) { if (!k) return false; for (int i=1;i<=a[k][0];i++) { int j=a[k][i]; if (!used[j]) { used[j]=true; if (!match[j]||cross(match[j])) { match[j]=k; return true; } } } return false; } void solve() { for (int i=1;i<=x;i++) { if (cross(i)) ans++; fill(used,used+5005,0); } } int main() { init(); solve(); cout<<ans<<endl; return 0; }