二分图之poj2446

以你之姓@ 2022-08-27 14:48 9阅读 0赞

题目：[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;
    }

[poj2446]: http://poj.org/problem?id=2446