首页 » 技术分享 » Chessboard（二分图最大匹配）

Chessboard（二分图最大匹配）

　
评论关闭　1,882次浏览

                                    Chessboard

Time Limit: 2000MS   Memory Limit: 65536K
Total Submissions: 20116   Accepted: 6325

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). 

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: 

 
A VALID solution.

 

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

 

 
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
Hint

 
A possible solution for the sample input.

Source

POJ Monthly,charlescpp

题意：棋盘上，要用1*2的木板覆盖，但是棋盘上有洞，覆盖的时候不能盖住洞，问你当前的图能否实现全覆盖

这道题是搜二分图最大匹配搜出来的，但我看了半天也没有看出怎么用匈牙利算法，遂读题解，发现真的用了，感觉很神奇。

把这个棋盘看成一个类似国际象棋的棋盘，黑白相间的那种。任何2个相邻的格子肯定是不同颜色的（黑和白）。经过研究发现，如果一个格子的行号和列号加起来为奇数，那与它相邻的格子的行号和列号加起来一定是偶数，如果一个格子的行号和列号加起来为偶数，那与它相邻的格子的行号和列号加起来一定是奇数。（盗用题解）

就这样匹配，但为了优化，我们引入vector来存边，省去了每次dfs时要扫一遍的尴尬。时间缩短了六倍，很开心hhh（虽然不缩短也能过。。。。）

确定一个点的下一个连接的点，可以搜一边上下左右四个点是否满足。

#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<cstring>
#define maxn 2000
#define pb push_back
using namespace std;

int n,m,k,x,y;
int atlas[maxn],vis[maxn],match[maxn];
vector<int> next[maxn];

int dfs(int cur)
{
    for(int i=0;i<next[cur].size();i++)
    {
        if(vis[next[cur][i]]) continue;
        vis[next[cur][i]]=1;
        if(!match[next[cur][i]]||dfs(match[next[cur][i]]))
        {
            match[cur]=next[cur][i];
            match[next[cur][i]]=cur;
            return 1;}
     }
    return 0;
}

int main()
{
    scanf("%d%d%d",&n,&m,&k);
    memset(atlas,0,sizeof(atlas));
    for(int i=1;i<=m*n;i++)
        next[i].clear();
    for(int i=0;i<k;i++)
        {
            scanf("%d%d",&x,&y);
            y--;
            atlas[x+y*m]=1;
        }
    if((n*m-k)&1)   {printf("NO\n");return 0;}
    for(int i=1;i<=m*n;i++)
    {
        if(i>m&&atlas[i-m]!=1){next[i].pb(i-m);}
        if(i<=m*(n-1)&&atlas[i+m]!=1) next[i].pb(i+m);
        if(i%m!=1&&atlas[i-1]!=1) next[i].pb(i-1);
        if(i%m&&atlas[i+1]!=1) next[i].pb(i+1);
    }
    int ans=0;
    for(int i=1;i<=n*m;i++)
        if(!atlas[i]&&!match[i])
        {    
            memset(vis,0,sizeof(vis));
            ans+=dfs(i);}
    if(ans*2==n*m-k)  printf("YES\n");
    else printf("NO\n");
    return 0;
}

 

转载自原文链接, 如需删除请联系管理员。

原文链接：Chessboard（二分图最大匹配），转载请注明来源！

赞 0