棋盘覆盖

思路：

一个骨牌覆盖两个相邻的格子，也就是相邻的格子有边相连，不相邻的格子没有边相连，所以可以分成两个集合，是偶数的和是奇数的分开，恰好与“0要素”对应。每个格子只能被1张骨牌覆盖，恰好与“1要素”对应。
将没有被禁止的格子分成左右两个集合，建一个左集合节点到右集合节点的有向图（根据具体实现的原理可以不需要右集合节点到左集合节点的边）是一张二分图。
最多有多少条匹配边就是这题的结果
复杂度有点高：
经常重复敲的代码尽量写成函数，写错了容易找到问题，也美观。

MyCode：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e4+7,maxm=2e4+7;
bool used[maxn],vis[107][107];
int boy[maxn];
int head[maxn],Next[maxm],to[maxm],tot;
inline ll read() {
    ll s = 0, w = 1;
    char ch = getchar();
    while (ch < 48 || ch > 57) {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= 48 && ch <= 57)
        s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
void add(int x,int y) {
    to[++tot]=y;
    Next[tot]=head[x];
    head[x]=tot;
}
bool dfs(int x) {
    for(int i=head[x],y; i; i=Next[i]) {
        if(!used[ y=to[i] ]) {
            used[y]=true;
            if(!boy[y]||dfs(boy[y])) {
                boy[y]=x;
                return true;
            }
        }
    }
    return false;
}
int n,m,ans;
int dis[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
void link(int a,int b) {
    int num1=n*(a-1)+b,num2;
    for(int i=0,x,y;i<4;++i) {
        x=a+dis[i][0],y=b+dis[i][1];
        num2=n*(x-1)+y;
        if(vis[x][y]||x<1||y<1||x>n||y>n) continue;
        add(num1,num2);
    }
}
int main() {
    n=read(),m=read();
    while(m--)
        vis[read()][read()]=true;
    for(int i=1,j;i<=n;i+=2)
    for(j=1;j<=n;j+=2) if(!vis[i][j]) link(i,j);
    for(int i=2,j;i<=n;i+=2)
    for(j=2;j<=n;j+=2) if(!vis[i][j]) link(i,j);
    for(int i=1,j,num; i<=n; i+=2)
        for(j=1,num=n*(i-1)-1; j<=n; j+=2) {
            num+=2;
            memset(used,false,sizeof used);
            if(!vis[i][j]&&dfs(num)) ans+=1;
        }
    for(int i=2,j,num; i<=n; i+=2)
        for(j=2,num=n*(i-1); j<=n; j+=2) {
            num+=2;
            memset(used,false,sizeof used);
            if(!vis[i][j]&&dfs(num)) ans+=1;
        }
    printf("%d\n",ans);
}