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 ...
一周排行
  • 51CTO.com昨日曾报道微软发布Visual Studio 2010 Beta 2和.NET 4的Beta 2的消息,普通用户今天已经可以获取免费下载.同时,微软还宣布了Visual Studio 2010的官方 ...
  • /*** * 测试统计API <br> * 小结:<br> * 1.逻辑代码应用{} 包起来 不写{} 默认 + return <br> * 2.重载方法参数必须加类型声明< ...
  • Android二次打包植入广告 我们拿HelloWord.apk为例,反编译植入有米广告. 首先,我们用apk改之理,反编译HelloWorld.apk. 然后按照有米的开发文档进行广告植入.下载地址http://s ...
  • 1.ul中的li居中:ul作导航时,想实现li垂直和水平居中,为ul添加text-align:center和line-height:100%,li用display:inline.如果用float的话,垂直不居中. 2 ...
  • 在我们的程序中,经常会有一些耗时较长的运算,为了保证用户体验,不引起界面不响应,我们一般会采用多线程操作,让耗时操作在后台完成,完成后再进行处理或给出提示,在运行中,也会时时去刷新界面上的进度条等显示,必要时还要控制 ...
  • <form onsubmit="return validateCallback(this)" class="pageForm" action="ajaxDone ...
  • 借助于apathe的poi.jar,由于上传文件不支持.jar所以请下载后将文件改为.jar,在应用程序中添加poi.jar包,并将需要读取的excel文件放入根目录即可. 本例使用java来读取excel的内容并展 ...
  • IPv6发展与部署之冷静思考 摘要:本文通过对比分析IPv6与IPv4的诸多特性,突出IPv6在未来网络发展中所具有的优势,并就IPv6网络如何有序发展提出了一些建议和看法,以期在IPv6网络的部署和建设中起到一定的 ...
  • 今天一个客户反映网站无法访问,检查服务器一切正常,查询域名发现域名状态为Domain Status: clientTransferProhibitedDomain Status: clientHold英文意思好懂,可 ...
  • 使用纯CSS来实现的一个响应式导航菜单,我们使用的是HTML5+CSS3技术,当浏览器窗口变小或者使用手机浏览器访问的时候,原本横条菜单会收缩成一个下拉菜单,当鼠标滑向菜单时下拉展示全部菜单 此方法可以应用到有特别多 ...