poj2446_二分图

POJ 2446  二分图的最大匹配 匈牙利算法

Chessboard
Time Limit: 2MS   Memory Limit: 65536K
Total Submissions: 14350   Accepted: 4471

Description

Alice and Bob often play games on chessboard. One day, Alice draws a board with size M * N. She wants Bob to use a lot of cards with size 1 * 2 to cover the board. However, she thinks it too easy to bob, so she makes some holes on the board (as shown in the figure below). 
poj2446_二分图

We call a grid, which doesn’t contain a hole, a normal grid. Bob has to follow the rules below: 
1. Any normal grid should be covered with exactly one card. 
2. One card should cover exactly 2 normal adjacent grids. 

Some examples are given in the figures below: 
poj2446_二分图
 
A VALID solution.

poj2446_二分图
 
An invalid solution, because the hole of red color is covered with a card.

poj2446_二分图
 
An invalid solution, because there exists a grid, which is not covered.

Your task is to help Bob to decide whether or not the chessboard can be covered according to the rules above.

Input

There are 3 integers in the first line: m, n, k (0 < m, n <= 32, 0 <= K < m * n), the number of rows, column and holes. In the next k lines, there is a pair of integers (x, y) in each line, which represents a hole in the y-th row, the x-th column.

Output

If the board can be covered, output "YES". Otherwise, output "NO".

Sample Input

4 3 2
2 1
3 3

Sample Output

YES

题意:用2*1的木板覆盖给定的棋盘(棋盘中有墙),木板不能重叠,问是否能全部覆盖
思路:奇偶建二分图,把棋盘涂成黑白相间,每个黑格和4个白格相邻,每个白格和四个黑格相邻,黑格移入U,白格移入V,求最大匹配,由于每个匹配对应两个结点,若最大匹配*2等于总结点数说明成功覆盖
poj2446_二分图
poj2446_二分图
/* poj2446 141ms  */
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;

const int maxn=1200;

int N,M,K;
int uN,vN;
vector<int> G[maxn];
int link[maxn];
bool vis[maxn];
int ch[maxn][maxn];
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};

bool dfs(int u)
{
    for(int i=0;i<G[u].size();i++){
        int v=G[u][i];
        if(!vis[v]){
            vis[v]=1;
            if(link[v]==-1dfs(link[v])){
                link[v]=u;
                return true;
            }
        }
    }
    return false;
}

int hungary()
{
    int res=0;
    memset(link,-1,sizeof(link));
    for(int u=1;u<=uN;u++){
        memset(vis,0,sizeof(vis));
        if(dfs(u)) res++;
    }
    return res;
}

int main()
{
    cin>>N>>M>>K;
    for(int i=1;i<=N*M;i++) G[i].clear();
    memset(ch,-1,sizeof(ch));
    uN=vN=0;
    while(K--){
        int i,j;
        scanf("%d%d",&j,&i);
        ch[i][j]=0;
    }
    for(int i=1;i<=N;i++){
        for(int j=1;j<=M;j++){
            if(ch[i][j]){
                if((i+j)%2) ch[i][j]=++uN;
                else ch[i][j]=++vN;
            }
        }
    }
    for(int i=1;i<=N;i++){
        for(int j=1;j<=M;j++){
            if(ch[i][j]&&ch[i][j]!=-1&&(i+j)%2){
                for(int k=0;k<4;k++){
                    int x=i+dx[k],y=j+dy[k];
                    if(ch[x][y]&&ch[x][y]!=-1) G[ch[i][j]].push_back(ch[x][y]);
                }
            }
        }
    }
    int match=hungary();
    if(match*2==uN+vN) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    return 0;
}
View Code

 

更多相关文章
  • 在我的上一篇博客中, 很多园友提出说对css3"画图"不是很理解, 在跟他们私聊了一段时间以后,加上自己在开始自学css3的时候的疑惑,我觉得大家之所以不是很理解主要是因为对伪元素不太了解,介于画图和CSS3里一些高大上的特效用的比较广泛的伪类元素就是::before 和 ::a ...
一周排行
  • 2009年,中国的网站数量为320万个,博客空间已达1.81亿个,网民数量达到3.6亿.互联网已经成为我们生活中不可分割且非常重要的一部分. 1.物联网成为热词 12月27日,温家宝总理时在中南海紫光阁接受新华社记者 ...
  • 时下,路由器已经变得与现代生活密不可分,无论是家庭娱乐抑或企业办公,它早已是一件必不可少的网络设备.因此,在满足用户上网的同时,厂商也不断加入了许多时尚元素,以满足消费者更多的需求.斐讯公司即将上市的FR625,就是 ...
  • 不在于你做什么.在于你怎么生活.你所说的前途是什么?钱途?还是幸福的人生.套用美国人的话,什么是幸福:1.做自己喜欢做的2.用自己喜欢做的养活自己3.在自己喜欢做的事上有所成就.
  • 严珺 发自柬埔寨吴哥窟 如果有一天,你站在吴哥窟的古寺前,只要你有一台能联网的手机或者平板,你就可以在亲身游览古迹的同时,在屏幕上看到一模一样的古迹,即使你还没有进入吴哥窟的古寺内,你都能清楚地看到里面的细节,然后通 ...
  • 来源:http://www.12reads.cn/23917.html 以 往,我们总认为战略的核心原则之一是:行业分析是战略分析的基本要素.但近日我观察到一个现象,这项核心原则已受到质疑.观察这些改变是有趣的:包括 ...
  • 1,Tomcat启动报错如下:Caused by: org.springframework.beans.factory.BeanCreationException: Error creating bean with ...
  • 航空公司为何陷入"经营之困"? 文/王易见 航空公司的问题似乎并没有我们想象的那么简单?       继前两天东航董事长刘绍勇抛出不能为携程打工的论调之后,今天又爆出国泰航空创纪录巨亏85.58亿 ...
  • 今天小编为大家带来了暗黑3 2.3什么时候更新 2.3补丁内容预览,感兴趣的朋友们可以跟着小编去下文了解一下哦. <暗黑3>2.3什么时候更新?2.3补丁内容预览.2.3.0补丁PTR服务器即将开放!大家 ...
  • 从我学Android开始,一直就想做一件事.就是好好把APIDemo看一遍.今天开始会抽时间把Android官方的APIDemo程序全部过一遍.主要是为了两个目的:第一,复习以前学习的API用法.第二,掌握Andro ...
  • wireshark过滤抓包时,capture fillter填写完后会崩溃的问题,报The link type of interface \Device\NPF_{11A6562D-E3B2BE-AEAA ...