POJ2446 Chessboard(二分图)

题意：

一个n*m的棋盘上有t个坑，要求用1*2的纸条完全覆盖这个棋盘，纸条不能盖上坑。

要点：

这题是二分图，就是求二分图的最大匹配，看是否与棋盘格子数-坑数相等。但是具体的集合很难想，看了网上题解，确实比较精妙。首先我们知道如果一个格子的行数+列数i+j是奇数，它相邻的格子的i+j必定为偶数，所以我们只要用i+j为奇数的为一个集合，偶数为一个集合，求出最大匹配数即可。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 1500
bool map[N][N], used[N];
int girl[N],path[50][50];
int n, m,t,odd,even;bool find(int x)
{for (int i = 1; i < even; i++){if (map[x][i] && used[i] == false){used[i] = true;if (girl[i] == -1 || find(girl[i])){girl[i] = x;return true;}}}return false;
}
void solve()
{int ans = 0;memset(girl, -1, sizeof(girl));for (int i = 1; i < odd; i++){memset(used, false, sizeof(used));if (find(i)) ans++;}if (ans * 2 == (m*n - t))//如果最大匹配数*2与总格子数相等说明成功printf("YES\n");elseprintf("NO\n");
}int main()
{int i, j;while (~scanf("%d%d", &n, &m)){memset(path, 0, sizeof(path));memset(map, false, sizeof(path));scanf("%d", &t);int y, x;for (i = 0; i < t; i++){scanf("%d%d", &x, &y);path[y][x] = -1;		//小心这里行列搞反}odd = even = 1;for (i = 1; i <= n; i++)for (j = 1; j <= m; j++){if (path[i][j] != -1){if ((i + j) % 2 == 1)//对应的奇数集合path[i][j] = odd++;//进行标号if ((i + j) % 2 == 0)//对应的偶数集合path[i][j] = even++;}}for (i = 1; i <= n; i++)for (j = 1; j <= m; j++){if (path[i][j] != -1 && (i + j) % 2 == 1)//（i+j）为奇数说明它四周都是偶数{if (path[i - 1][j] >= 1)map[path[i][j]][path[i - 1][j]] = true;if (path[i + 1][j] >= 1)map[path[i][j]][path[i + 1][j]] = true;if (path[i][j-1] >= 1)map[path[i][j]][path[i][j-1]] = true;if (path[i][j+1] >= 1)map[path[i][j]][path[i][j+1]] = true;}}solve();}return 0;
}