题意：

给你一个n*n的矩阵，然后再给你几个坑，然后问你能否被1*2的长方形给覆盖；

• -弱知道了是二分匹配的做法，但是弱还是不会转化，又是在建图上GG了

分析：

从国际象棋的那个黑白色理解，这是一张二分图（好像非常有道理）

建图：由于是1*2的纸片覆盖，那么这个区域的两个点的（i+j）必然是一个奇数和一个偶数。

先搞好点，我们分别给奇数、偶数点 依次从1开始标号，相邻的就是有一条边；

这波建图好是经典；

一般建图弱感觉就是：先搞点，再建图，有些还会再初始化一波；

然后就是求一下最大匹配，

如果最大匹配+K=N*M就输出”YES”，否则就是”NO”

#include<iostream>

#include<stdio.h>

#include<string.h>

#include<map>

#include<stack>

#include<algorithm>

using namespace std;

#define N 1500

int ma[N][N];

int ls[N][N];

int n,m,t;

int cx[N];

int cy[N];

int ji,ou;

bool vis[N];

int findpath(int u)

{

    for(int i=1;i<ou;i++)

    {

        if(!vis[i]&&ma[u][i])

        {

            vis[i]=1;

            if(cy[i]==-1||findpath(cy[i]))

            {

                cx[u]=i;

                cy[i]=u;

                return 1;

            }

        }

    }

    return 0;

}

void solve()

{

    memset(cx,-1,sizeof(cx));

    memset(cy,-1,sizeof(cy));

    int ans=0;

    for(int i=1;i<ji;i++)

    {

            memset(vis,0,sizeof(vis));

            ans+=findpath(i);

    }

    ans*2==(m*n-t)?printf("YES\n"):printf("NO\n");

}

int main()

{

    while(~scanf("%d%d",&n,&m))

    {

        scanf("%d",&t);

        memset(ls,0,sizeof(ls));

        for(int i=0;i<t;i++)

        {

            int x,y;

            scanf("%d%d",&x,&y);

            ls[y][x]=-1;

        }

        ji=ou=1;

        for(int i=1;i<=n;i++)

        {

            for(int j=1;j<=n;j++)

            {

                if(ls[i][j]!=-1)

                {

                    if((i+j)%2==0)

                        ls[i][j]=ji++;

                    else

                        ls[i][j]=ou++;

                }

            }

        }

        memset(ma,0,sizeof(ma));

        for(int i=1;i<=n;i++)

        {

            for(int j=1;j<=m;j++)

            {

                if(ls[i][j]!=-1&&(i+j)%2==1)

                {

                    if(ls[i-1][j]>=1)

                        ma[ls[i-1][j]][ls[i][j]]=1;

                    if(ls[i+1][j]>=1)

                        ma[ls[i+1][j]][ls[i][j]]=1;

                    if(ls[i][j-1]>=1)

                        ma[ls[i][j-1]][ls[i][j]]=1;

                    if(ls[i][j+1]>=1)

                        ma[ls[i][j+1]][ls[i][j]]=1;

                }

            }

        }

        solve();

    }

    return 0;

}

[ls[i][j]]=1;

                }

            }

        }

        solve();

    }

    return 0;

}