首页 > 其他 > 详细

POJ 2446 二分图匹配

时间:2014-05-14 00:16:57      阅读:457      评论:0      收藏:0      [点我收藏+]

    题意:给你一个n*m方格 让你用1*2的的小方格去铺满,其中有k个方格不能被铺到。


   思路:二分图建图, 以每个格子为点建图,如果可以用一块1*2的小方格铺到,就连一条边。

           每个格子在X集合和Y集合都有一个点,只要任意一边被匹配到了就算可以,然后就是二分图匹配了。

  上代码。


#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<vector>
#include<stack>
#include<math.h>
#define maxn 32*32+5
using namespace std;
vector<int> G[maxn];
int macx[maxn];
int macy[maxn];
bool check[maxn];
int N;
void init()
{
    for(int i=0;i<N;i++)
        G[i].clear();
}
void add_edge(int from,int to)
{
    G[from].push_back(to);
}
bool dfs(int u)
{
    for(int i=0;i<G[u].size();i++)
    {
        int v=G[u][i];
        if(!check[v])
        {
            check[v]=1;
            if((macy[v]==-1&&macx[v]==-1))
            {
                macx[u]=v;
                macy[v]=u;
                macy[u]=-1;
                macx[v]=-1;
                return 1;
            }
            else if(macy[v]==-1&&dfs(macx[v]))
            {
                macx[u]=v;
                macy[v]=u;
                macy[u]=-1;
                macx[v]=-1;
                return 1;
            }
            else if(macx[v]==-1&&dfs(macy[v]))
            {
                macx[u]=v;
                macy[v]=u;
                macy[u]=-1;
                macx[v]=-1;
                return 1;
            }
        }
    }
    return 0;
}
int xyl()
{
    memset(macx,-1,sizeof(macx));
    memset(macy,-1,sizeof(macy));
    int ans=0;
    for(int i=0;i<N;i++)
    {
        if(macx[i]==-1&&macy[i]==-1)
        {
            memset(check,0,sizeof(check));
            if(dfs(i))
            {
                //printf("%d\n",i);
                ans++;
            }
        }
    }
    return ans;
}
bool mp[50][50];
int x[4]={1,0,-1,0};
int y[4]={0,1,0,-1};
int main()
{
    int n,m,k;
    while(scanf("%d%d%d",&n,&m,&k)!=EOF)
    {
        int k1=k;
        memset(mp,0,sizeof(mp));
        while(k1--)
        {
            int A,B;
            scanf("%d%d",&A,&B);
            mp[B-1][A-1]=1;
        }
        if((n*m-k)%2==1)
        {
            printf("NO\n");
            continue;
        }
        N=n*m;
        init();
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
            {
                int p=i*m+j;
                if(mp[i][j]==1) continue;
                for(int k=0;k<4;k++)
                {
                    int nx=i+x[k];
                    int ny=j+y[k];
                    if(nx>=0&&ny>=0&&nx<n&&ny<m&&mp[nx][ny]==0)
                    {
                        int p1=nx*m+ny;
                        add_edge(p,p1);
                    }
                }
            }
        int ans=xyl();
        int p=(n*m-k)/2;
        //printf("%d\n",ans);
        if(ans==p)
            printf("YES\n");
        else printf("NO\n");
    }
}


POJ 2446 二分图匹配,布布扣,bubuko.com

POJ 2446 二分图匹配

原文:http://blog.csdn.net/u012896700/article/details/25627805

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!