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 ...
一周排行
  • 10月23日消息,苹果今日凌晨正式发布了iPad Air和视网膜屏iPad mini.以下是各大外媒对两款新iPad的点评汇总:华尔街日报苹果今天发布了两款新iPad--iPad Air和视网膜屏iPad mini, ...
  • 体系结构图 1 显示在 ASP.NET 中驻留远程对象时的基本 .NET Remoting 体系结构.如果主要关心安全性问题,那么建议使用 ASP.NET 主机和 HTTP通道进行通信,因为它允许远程对象利用 ASP ...
  • ============================================================博文原创,转载请声明出处电子咖啡(原id蓝岩)========================= ...
  •    keyPath分为:transform.scale     transform.scale.x      transform.scale.y      transform.scale.z      CABasi ...
  • gulp 是前端开发过程中对代码进行构建(Build)的工具,类似于Java世界中的Ant或者Maven.与Ant或Maven类似,在用gulp进行build时,经常需要顺序执行任务:在前一个任务彻底结束后才开始下一 ...
  • void * memcpy(void * dst, const void * src, size_t count) { void *res=dst; while (count--) { *(char*)dst = * ...
  • 引自图灵教育陈冰老师的我第一次看谭老师的<C程序设计>,是20年前,那时我17岁,大学一年级.当时感觉这本书很神奇,对编程充满了好奇.同时也感觉这本书有些难,有些地方,比如指针,虽然看过书,也有老师讲过了 ...
  • 1. 中断向量表:     中断向量表即中断处理程序入口地址的列表.     8086CPU,中断向量表必须放在000~3FF单元中.     每个中断向量占32位内存地址空间(低十六位为偏移 ...
  • unction encrypt(ecode)Dim textsdim i for i=1 to len(ecode)texts=texts & chr(asc(mid(ecode,i,1))+i)nexten ...
  • 在eclipse里配置Android ndk环境 适用于windows mac 和linux(转)   7 6  分类: android   标签:java  program  and ...