POJ 2446 Chessboard（二分图匹配）

本文主要是介绍POJ 2446 Chessboard（二分图匹配），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

POJ 2446 Chessboard

题目链接

题意：给定一个棋盘，上面有洞，问能否完美用1 * 2纸条铺满，纸条不能重叠，不能贴到洞上

思路：二分图匹配，求最大独立集，相邻的空白建边即可，然后这题有一个很坑的地方啊，就是输入洞的位置(x, y)居然是先输y再输x，这不合常理坑爹

代码：

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;const int N = 35;
const int d[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};int n, m, k, graph[N][N];
vector<int> g[N * N];
int left[N * N], vis[N * N];bool dfs(int u) {for (int i = 0; i < g[u].size(); i++) {int v = g[u][i];if (vis[v]) continue;vis[v] = 1;if (left[v] == -1 || dfs(left[v])) {left[v] = u;return true;}}return false;
}int hungary() {int ans = 0;memset(left, -1, sizeof(left));for (int i = 0; i < n * m; i++) {memset(vis, 0, sizeof(vis));if (dfs(i)) ans++;}return ans;
}int main() {while (~scanf("%d%d%d", &n, &m, &k)) {int x, y;memset(graph, 0, sizeof(graph));for (int i = 0; i < k; i++) {scanf("%d%d", &y, &x);x--; y--;graph[x][y] = 1;}for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {g[i * m + j].clear();if (graph[i][j]) continue;for (int k = 0; k < 4; k++) {int x = i + d[k][0];int y = j + d[k][1];if (x < 0 || x >= n || y < 0 || y >= m || graph[x][y]) continue;g[i * m + j].push_back(x * m + y);}}}printf("%s\n", n * m - k == hungary() ? "YES" : "NO");}return 0;
}

这篇关于POJ 2446 Chessboard（二分图匹配）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---