题目描述

给出一张nn(n< =100)的国际象棋棋盘，其中被删除了一些点，问可以使用多少12的多米诺骨牌进行掩盖。

输入格式

第一行为n，m（表示有m个删除的格子） 第二行到m+1行为x,y，分别表示删除格子所在的位置 x为第x行 y为第y列

输出格式

一个数，即最大覆盖格数

样例输入

8 0

样例输出

32

RT，显然是二分图匹配做，但是居然 WA 而且只有 $18pts$，求大佬帮我调一下

#include<bits/stdc++.h>
#define MAXN 110
#define MAXM 10010
using namespace std;
struct edge{
    int pre,to;
};
edge e[MAXM << 2];
int n,m,p,cnt;
int head[MAXM],id[MAXN][MAXN],cp[MAXM];
bool isdelete[MAXN][MAXN],vis[MAXM];
void add_edge(int u,int v){
    e[++cnt].pre = head[u];
    e[cnt].to = v;
    head[u] = cnt;
}
bool dfs(int now){
    for(int i = head[now]; i; i = e[i].pre){
        if(vis[e[i].to]) continue;
        vis[e[i].to] = true;
        if(!cp[e[i].to] || dfs(e[i].to)){
            cp[e[i].to] = now;
            cp[now] = e[i].to;
            return true;
        }
    }
    return false;
}
void match(){
    int res = 0;
    for(int i = 1; i <= p; i++){
        memset(vis, 0, sizeof(vis));
        if(dfs(i)) res++;
    }
    printf("%d\n",res);
}
int main(){
    scanf("%d%d",&n, &m);
    for(int i = 1; i <= m; i++){
        int x,y; scanf("%d%d",&x, &y);
        isdelete[x][y] = true;
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(!isdelete[i][j]) id[i][j] = ++p;
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = (i % 2) ? 1 : 2; j <= n; j += 2){
            if(isdelete[i][j]) continue;
            if(id[i][j + 1]) add_edge(id[i][j],id[i][j + 1]);
            if(id[i][j - 1]) add_edge(id[i][j],id[i][j + 1]);
            if(id[i + 1][j]) add_edge(id[i][j],id[i + 1][j]);
            if(id[i - 1][j]) add_edge(id[i][j],id[i - 1][j]);
        }
    }
    match();
    return 0;
}