题目描述

给定一个N行N列的棋盘，已知某些格子禁止放置。

求最多能往棋盘上放多少块的长度为2、宽度为1的骨牌，骨牌的边界与格线重合（骨牌占用两个格子），并且任意两张骨牌都不重叠。

输入格式
第一行包含两个整数N和t，其中t为禁止放置的格子的数量。

接下来t行每行包含两个整数x和y，表示位于第x行第y列的格子禁止放置，行列数从1开始。

输出格式
输出一个整数，表示结果。

数据范围
1≤N≤100

样例

输出样例：
8 0
输出样例：
32

算法1

(EK) $O(n^5)$

二分图板子题，怎么能没有我大$EK$题解哪（虽然会$Dinic$的人都不用$EK$了，但我是蒟蒻啊）
用最大流求解二分图最大匹配书里讲得很清楚了，这里就不赘述了，代码仅供参考

一定要注意边界条件，禁用格子的条件，要不然一不小心就会WA

时间复杂度

$O(n^5)$
但一般来讲没有这么大，谨慎起见用火车头卡卡常

C++ 代码

#pragma GCC target("sse,sse2,sse3,sse4.1,sse4.2,popcnt,abm,mmx,avx")
#pragma comment(linker,"/STACK:102400000,102400000")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include<bits/stdc++.h>
using namespace std;
const int inf=1000000000;
const int N=100000;
int v[N],edge[N],nxt[N],head[N],q[N],liu[N],last[N],n,n1,n2,m,s,t,i,j,tot,l,r,ans,x,y,z;
bool use[N],notuse[200][200];
void pu(int x,int y,int z) {
    v[++tot]=y;
    edge[tot]=z;
    nxt[tot]=head[x];
    head[x]=tot;
    v[++tot]=x;
    edge[tot]=0;
    nxt[tot]=head[y];
    head[y]=tot;
}
int bfs() {
    int i,l,r,xx,yy;
    memset(use,0,sizeof(use));
    memset(q,0,sizeof(q));
    use[s]=true;
    q[1]=s;
    liu[s]=inf;
    l=1; r=1;
    while (l<=r) {
        xx=q[l];
        l++;
        for (i=head[xx]; i; i=nxt[i])
            if (edge[i]) {
                yy=v[i];
                if (use[yy]) continue;
                liu[yy]=min(liu[xx],edge[i]);
                last[yy]=i;
                r++;
                q[r]=yy;
                use[yy]=true;
                if (yy==t) return true;
            }
    }
    return false;
}
void update() {
    int x,i;
    x=t;
    while (x!=s) {
        i=last[x];
        edge[i]-=liu[t];
        edge[i^1]+=liu[t];
        x=v[i^1];
    }
    ans+=liu[t];
}
int main() {
    scanf("%d%d",&n,&m);
    n=n;
    s=n*n+1; t=n*n+2;
    ans=0;
    tot=1;
    for (i=1; i<=m; i++) {
        scanf("%d%d",&x,&y);
        notuse[x][y]=true;
    }
    for (i=1;i<=n;i++)
    {
        for (j=1;j<=n;j++)
        {
            if (notuse[i][j]) continue;
            if ((i+j)%2==0) pu(s,(i-1)*n+j,1);
            else pu((i-1)*n+j,t,1);
            if (!notuse[i][j+1] && j!=n) 
            {
                if ((i+j)%2==0) pu((i-1)*n+j,(i-1)*n+j+1,1);
                else pu((i-1)*n+j+1,(i-1)*n+j,1);
            }
            if (!notuse[i+1][j] && i!=n) 
            {
                if ((i+j)%2==0) pu((i-1)*n+j,i*n+j,1);
                else pu(i*n+j,(i-1)*n+j,1);
            }
        }
    }
    while (bfs()) update();
    cout<<ans<<endl;
    return 0;
}
//一个赤裸裸的板子