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 ...
一周排行
  • EXEC sp_configure show advanced options, 1;RECONFIGURE;EXEC sp_configure xp_cmdshell, 1;RECONFIGURE;-- dbcc ...
  • 马晓芳千呼万唤之中,中国的4G牌照终于在今年的12月4日正式发放.无论是对于设备商.终端商,还是对于应用商.服务商,以及个人消费者都将是一场盛宴.日前,参加中国移动全球合作伙伴大会的中国移动总裁李跃接受了<第一 ...
  • 问题描述:       连接wifi,选择在线升级,在现在升级包过程中,提示网络异常,导致升级失败. 问题解决:     首先分析mainlog中对应时间点上下文的log.通过搜索rssi,查看当前wifi连接状态, ...
  • 5月27日,据<纽约时报>报道,Facebook很有可能将于明年推出自己的智能手机.此前也有过几次Facebook要开发智能手机的传言,比如项目代号"Buffy",合作方可能有三星和H ...
  • JMS简介 JMS源于企业应用对于消息中间件的需求,使应用程序可以借助消息进行异步处理而互不影响.Sun公司和它的合作伙伴设计的JMS API定义了一组公共的应用程序接口和相应语法,使得Java程序能够和其他消息组件 ...
  • 131 Palindrome Partitioning  这道题先是标识出所有的 s[i:j+1] 是否为 palindrome, 然后在暴力搜索就好 class Solution: def __init__(sel ...
  • 间隔着取_(:зゝ∠)_ #include #include #include using namespace std; typedef long long ll; int n, m; int init(int i, ...
  • 转贴过来,方便自己查阅 工作原理: 一边服务器的网络子网为192.168.1.0/24 路由器为100.10.15.1 另一边的服务器为192.168.10.0/24 路由器为200.20.25.1. 执行下列步骤: ...
  •       局里突然通知我要传一张一寸电子相片回去,要求是白底的.于是从我的文档找了一下,发现有一张红底的照片,想想,把红底改成白底就可以了,省得再去照一张.       右键打开文件关联菜单找Fireworks,怪 ...
  • 随着互联网的普及,IT管理人员面临着更为复杂和频繁的网络安全问题,病毒.恶意攻击日渐增多,80端口上不再只有web服务,QQ也不再只是一个聊天工具,并且以经济利益为目的的网络攻击日益成为主流,而传统基于L3.L4的网 ...