称号：

id=2446">poj2446

意甲冠军：给定一个m*n矩阵，在有些地方坑，然后1*2本文叠加，反复。可以把出了坑的地方其它所有覆盖的话输出YES，否则NO

分析：有一道二分图经典题目，当然难点还是建图，一直没有思路，早上来忽然想到能够用（i-1）*m+j 吧矩阵中每一个点转化为一个数，然后相邻连接起来建图，匈牙利，可是不知道为什么不正确？求大神解释、还是理解不够深。

非常多人都是按其奇偶性建图的，由于要用1*2的纸片覆盖，那么两个值（i+j）必定一个奇数一个偶数。然后分别给图中的奇数偶数点依次从1開始标号，相邻的按其标号建图。匈牙利、、比較高速。正解！

由于必定是一个奇数点相应一个相邻偶数点。那么仅仅要求随意奇数或偶数的最大匹配就能够了。经典的建图方法。

代码：

#include <cstdio>

#include <cstring>

#include <string>

#include <iostream>

#include <algorithm>

#include <cmath>

using namespace std;

const int N = 1200;

#define Del(x,y) memset(x,y,sizeof(x))

int map[N][N],link[N],vis[N],vlink[N];

int path[50][50];

int n,m,t,tmp1,tmp2;

bool dfs(int x)

{

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

    {

        if(map[x][i]==1 && vis[i]==0)

        {

            vis[i]=1;

            if(link[i]==-1 || dfs(link[i]))

            {

                link[i]=x;

                return true;

            }

        }

    }

    return false;

}

void solve()

{

    int ans=0;

    Del(link,-1);

    Del(vlink,-1);

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

    {

        Del(vis,0);

        if(dfs(i))

            ans++;

    }

    //printf("%d\n",ans);

    if(ans*2==(m*n-t))

        printf("YES\n");

    else

        printf("NO\n");

}

int main()

{

    //freopen("Input.txt","r",stdin);

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

    {

        Del(path,0);

        int x,y;

        scanf("%d",&t);

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

        {

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

            path[y][x]=-1;

        }

        tmp1=1,tmp2=1;

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

        {

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

            {

                if(path[i][j]==0)

                {

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

                        path[i][j]=tmp1++;

                    else

                        path[i][j]=tmp2++;

                }

            }

        }

        Del(map,0);

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

        {

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

            {

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

                {

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

                        map[path[i-1][j]][path[i][j]]=1;

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

                        map[path[i+1][j]][path[i][j]]=1;

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

                        map[path[i][j-1]][path[i][j]]=1;

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

                        map[path[i][j+1]][path[i][j]]=1;

                }

            }

        }

        solve();

    }

    return 0;

}