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 ...
一周排行
  • 日前,谷歌公司表示,建设超速奥斯汀光纤网络正在顺利进行中.这个光纤网络将为奥斯汀带来超速1Gb网络服务. 周二(9月23日),谷歌光纤奥斯汀运营负责人Mark Stram表示,当地的光纤网络建设正在有序开展,网络包括 ...
  • 一.[前言] (1)本文将用到IOC框架Unity,可参照<Unity V3 初步使用 —— 为我的.NET项目从简单三层架构转到IOC做准备>(2)本文的解决方案是基于前述<使用IdleTest进 ...
  • 今日,微软将发布新一代操作系统Windows 10.值得一提的是,这次正版Win7/Win8.1用户可免费升级Windows 10正式版,Windows XP/Vista等用户则需通过购买获得. 另外,根据市场调研公 ...
  • 很多时候,我们不需要关心这个类,我们很少继承这个类,偶尔会调用这个类的api来实现一些功能,但是不可否认,这个类是iOS编程中很重要的一个概念,所以我这里写这个文章来总结以下这个类的信息,如果写的不对的地方,请留言, ...
  • 二.使用FTP方式 步骤1.在PC机"开始菜单"的"运行"栏中键入"cmd",进入DOS界面,保证PC机可以PING通设备. 步骤2.在交换机上启动FTP服 ...
  • JAVA字符串占位符替换  如果有字符串 "我是{0},我来自{1},今年{2}岁. 请问怎样用String的内置方法用替换掉字符串的占位符:比如"我是中国人,我来自北京,今年22岁". ...
  • 版权声明:原创作品,允许转载,转载时请务必以超链接形式标明文章原始出版.作者信息和本声明.否则将追究法律责任.http://blog.csdn.net/topmvp - topmvpContemporary soci ...
  • 上周,备受市场关注的蓝色巨人IBM公布其第一季度业绩,但低于预期的盈利,不仅让其股价创下近8年来最大单日跌幅,更令"股神"巴菲特一日损失12亿美元.系统与技术项目下滑最快创立于1911年的IBM公 ...
  • 题意: 给出一个有向带权图,求从起点到终点的两条不相交路径使得权值和最小. 分析: 第一次听到“拆点法”这个名词. 把除起点和终点以外的点拆成两个点i和i',然后在这两点之间连一条容量为1,费用为0的边.这样就保证了 ...
  •   本文转载至  http://www.cnblogs.com/wuyijibei/archive/2013/08/01/3230468.html   1: 首先, 所有的语言资源还是需要和现在的i18n方法一样,写 ...