[数据结构与算法]【POJ 2446】Chessboard（网络流）

Chessboard

题目链接：POJ 2446

题目大意

给你一个网格图，然后有一些地方已经有东西了。
然后问你能否放若干个 1*2 大小的东西使得每个地方都有东西。

思路

考虑从 $1?2$ 这个大小入手。
发现如果我们把网格图黑白染色，它这个 $1?2$ 就是两个相邻的不同颜色的点。

那我们就考虑把这个过程看做配对，然后你就把图建出来配对一下根据最大匹配看看是否所有位置都被匹配就可以啦。

代码

#include<queue> 
#include<cstdio>
#include<iostream>
#define INF 0x3f3f3f3f3f3f3f3f

using namespace std;

const int N = 32 + 5;
const int M = N * N + 100;
int n, m, k, x, y;
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};//上下左右四个方向 
struct node {
	int x, to, nxt, op;
}e[(M * M) << 1];
int le[M << 1], KK, S, T, tot;
int lee[M << 1], deg[M << 1];
bool hol[N][N];

bool check(int x, int y) {//判断点是否在图中 
	if (x < 1 || x > n) return 0;
	if (y < 1 || y > m) return 0;
	return 1;
} 

//网络流模板 
void add(int x, int y, int z) {
	e[++KK] = (node){z, y, le[x], KK + 1}; le[x] = KK;
	e[++KK] = (node){0, x, le[y], KK - 1}; le[y] = KK;
}

bool bfs() {
	for (int i = 1; i <= tot; i++) lee[i] = le[i], deg[i] = 0;
	queue <int> q; q.push(S); deg[S] = 1;
	while (!q.empty()) {
		int now = q.front(); q.pop();
		for (int i = le[now]; i; i = e[i].nxt)
			if (e[i].x && !deg[e[i].to]) {
				deg[e[i].to] = deg[now] + 1;
				if (e[i].to == T) return 1; q.push(e[i].to);
			}
	}
	return 0;
}

int dfs(int now, int sum) {
	if (now == T) return sum;
	int go = 0;
	for (int &i = lee[now]; i; i = e[i].nxt)
		if (e[i].x && deg[e[i].to] == deg[now] + 1) {
			int this_go = dfs(e[i].to, min(sum - go, e[i].x));
			if (this_go) {
				e[i].x -= this_go; e[e[i].op].x += this_go;
				go += this_go; if (go == sum) return go;
			}
		}
	if (go != sum) deg[now] = -1; return go;
}

int dinic() {
	int re = 0;
	while (bfs()) re += dfs(S, INF);
	return re;
}

int main() {
	scanf("%d %d %d", &n, &m, &k);
	
	if ((n * m - k) & 1) {//只有奇数个空位肯定不行（不过不判也可以） 
		printf("NO"); return 0;
	}
	
	tot = n * m; S = ++tot; T = ++tot;
	for (int i = 1; i <= k; i++) {
		scanf("%d %d", &y, &x); hol[x][y] = 1;//注意读入是y,x，看好题目意思 
	}
	
	for (int i = 1; i <= n; i++)//建图 
		for (int j = 1; j <= m; j++) {
			if (hol[i][j]) continue;
			if ((i + j) & 1) {
				add(S, (i - 1) * m + j, 1);
				for (int k = 0; k < 4; k++) {
					int x = i + dx[k], y = j + dy[k];
					if (hol[x][y] || !check(x, y)) continue;//这个位置是洞或者在边界外就不行 
					add((i - 1) * m + j, (x - 1) * m + y, 1);
				}
			}
			else add((i - 1) * m + j, T, 1); 
		}
	
	if (dinic() * 2 == n * m - k) printf("YES");
		else printf("NO");
	
	return 0;
}