ZOJ 1516 二分匹配
题意：给你n*m的土地，有k个1*1的方块被挖掉， 现在你要卖剩下的地(<=50)，地只能是1*2 或2*1卖，问你最多能卖几块。
思路：剩下的点按奇偶分成两列点阵(i+j为奇数就是奇点，反之就是偶点)。二分匹配可解
#include <cstdio>#include <cstring>#include <algorithm>#include <vector>using namespace std;const int maxn = 55;int n, m, k;bool map[103][103];int idx[103][103];int id;vector <int> edge[maxn];int pre[maxn];bool vis[maxn];bool dfs(int u) {for(int i = 0; i < (int) edge[u].size(); i++) {int v = edge[u][i];if(vis[v])continue;vis[v] = 1;if(pre[v] == -1 || dfs(pre[v])) {pre[v] = u;return 1;}}return 0;}int dir[4][2] = { -1, 0, 1, 0, 0, 1, 0, -1 };int main() {int i, j;while(~scanf("%d%d", &n, &m) && n && m) {scanf("%d", &k);int x, y;memset(map, 0, sizeof(map));while(k--) {scanf("%d%d", &x, &y);x--; y--;map[x][y] = 1;}id = 0;for(i = 0; i < n; i++)for(j = 0; j < m; j++)if(!map[i][j])idx[i][j] = id++;for(i = 0; i < id; i++)edge[i].clear();for(i = 0; i < n; i++)for(j = 0; j < m; j++)if(!map[i][j] && (i + j & 1)) {for(k = 0; k < 4; k++) {int x = i + dir[k][0];int y = j + dir[k][1];if(x < 0 || x >= n || y < 0 || y >= m || map[x][y])continue;edge[idx[i][j]].push_back(idx[x][y]);}}memset(pre, -1, sizeof(int) * id);int cnt = 0;for(i = 0; i < n; i++)for(j = 0; j < m; j++)if(!map[i][j] && (i + j & 1)) {memset(vis, 0, sizeof(bool) * id);if(dfs(idx[i][j])) cnt++;}printf("%d\n", cnt);}return 0;}