POJ 2446 Chessboard (二分图匹配)

题意

在一个N*M的矩形里，用1*2的骨牌去覆盖该矩形，每个骨牌只能覆盖相邻的两个格子，问是否能把每个格子都盖住。PS：有K个孔不用覆盖。

思路

容易发现,棋盘上坐标和为奇数的点只会和坐标和为偶数的点相邻,所以这是个二分图.而每两个格子对应一个骨牌，并且一个格子只能被一个骨牌覆盖，这样就联想到了二分图匹配。把图中能覆盖的格子从1 依次标号 若格子数为奇数 答案是NO 否则，把相邻的两个标号能连成一条边，求无向图的二分匹配数，当匹配数 == 格子数时，就能覆盖完。

代码

 

#include 
#include 
#include 
#include 
#include 
#include 
#define MID(x,y) ((x+y)/2)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
const int MAXV = 2005;                   //N1+N2
vector  adj[MAXV];
struct MaximumMatchingOfBipartiteGraph{
    int vn;
    void init(int n){                   //二分图两点集点的个数
        vn = n;
        for (int i = 0; i <= vn; i ++)     adj[i].clear();
    }
    void add_uedge(int u, int v){
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    bool vis[MAXV];
    int mat[MAXV];                      //记录已匹配点的对应点
    bool cross_path(int u){
        for (int i = 0; i < (int)adj[u].size(); i ++){
            int v = adj[u][i];
            if (!vis[v]){
                vis[v] = true;
                if (mat[v] == 0 || cross_path(mat[v])){
                    mat[v] = u;
                    mat[u] = v;
                    return true;
                }
            }
        }
        return false;
    }
    int hungary(){
        mem(mat, 0);
        int match_num = 0;
        for (int i = 1; i <= vn; i ++){
            mem(vis, 0);
            if (!mat[i] && cross_path(i)){
                match_num ++;
            }
        }
        return match_num;
    }
}match;
bool hole[35][35];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
void build(int m, int n){
    for (int i = 1; i <= m; i ++){
        for (int j = 1; j <= n; j ++){
            if (!hole[i][j]){
                for (int direction = 0; direction < 4; direction ++){
                    int x = i + dx[direction], y = j + dy[direction];
                    if (x > 0 && x <= m && y > 0 && y <= n && hole[x][y] == false){
                        match.add_uedge((i-1)*n+j, (x-1)*n+y);
                    }
                }
            }
        }
    }
}
int main(){
	//freopen("test.in", "r", stdin);
	//freopen("test.out", "w", stdout);
	int m, n, k;
	while(scanf("%d %d %d", &m, &n, &k) != EOF){
        mem(hole, 0);
        for (int i = 0; i < k; i ++){
            int y, x;
            scanf("%d %d", &y, &x);
            hole[x][y] = true;
        }
        if ((m * n - k) % 2 == 1){
            puts("NO");
        }
        else{
            int num = (m * n - k) / 2;
            match.init(m*n);
            build(m, n);
            if (match.hungary() == num){
                puts("YES");
            }
            else{
                puts("NO");
            }
        }
	}
	return 0;
}