CH6801 棋盘覆盖（二分图最大匹配）

冷不防 2021-11-13 23:34 274阅读 0赞

## 题意：给定一个 N\*N 的棋盘，棋盘上有些位置不能防止任何东西，现用 1\*2 的骨牌填充棋盘，问最多能铺多少块骨牌。 ##

## 分析：和骑士共存差不多的经典题，算是板子题，详见《算法竞赛进阶指南》P422，状压dp（插头dp）也可以做。 ##

## 代码： ##

#include <cstdio>
    #include <vector>
    #include <cstring>
    #include <iostream>
    using namespace std;
    const int N = 106;
    const int dx[4] = {0,0,1,-1};
    const int dy[4] = {1,-1,0,0};
    int n, m, ans, f[N*N];
    bool b[N][N], v[N*N];
    vector<int> e[N*N];
    
    bool dfs(int x) {
    	for (unsigned int i = 0; i < e[x].size(); i++) {
    		int y = e[x][i];
    		if (v[y]) continue;
    		v[y] = 1;
    		if (f[y] == -1 || dfs(f[y])) {
    			f[y] = x;
    			return 1;
    		}
    	}
    	return 0;
    }
    
    int main() {
    	cin >> n >> m;
    	while (m--) {
    		int x, y;
    		scanf("%d %d", &x, &y);
    		b[x-1][y-1] = 1;
    	}
    	for (int i = 0; i < n; i++)
    		for (int j = 0; j < n; j++)
    			if (!b[i][j])
    				for (int k = 0; k < 4; k++) {
    					int x = i + dx[k], y = j + dy[k];
    					if (x >= 0 && x < n && y >= 0 && y < n && !b[x][y]) {
    						e[i*n+j].push_back(x * n + y);
    						e[x*n+y].push_back(i * n + j);
    					}
    				}
    	memset(f, -1, sizeof(f));
    	for (int i = 0; i < n; i++)
    		for (int j = 0; j < n; j++) {
    			if ((i ^ j) & 1) continue;
    			memset(v, 0, sizeof(v));
    			ans += dfs(i * n + j);
    		}
    	cout << ans << endl;
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，274人围观）

还没有评论，来说两句吧...

相关阅读

相关二分图最大匹配 hdoj 1045

题目：[hdoj1045][] 题意：给出一个图，其中有 . 和 X 两种，. 为通路，X表示墙，在其中放炸弹，然后炸弹不能穿过墙，问你最多在图中可以放多少个炸弹？

àì夳堔傛蜴生んèń/ 2022年08月27日 14:46/ 0 赞/ 180 阅读

相关二分图最大匹配

\[POJ 3041\] ([http://poj.org/problem?id=3041][http_poj.org_problem_id_3041]) 题目描述： A

Dear 丶/ 2022年08月04日 11:44/ 0 赞/ 176 阅读

相关 Gopher（二分图最大匹配）

Problem K: Gopher Time Limit: 1 Sec Memory Limit: 128 MB Submit: 5 Solved: 4

￡神魔★判官ぃ/ 2022年08月01日 03:16/ 0 赞/ 194 阅读

相关 HDU1281棋盘游戏-最大二分匹配

棋盘游戏 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Othe

忘是亡心i/ 2022年07月12日 05:03/ 0 赞/ 148 阅读

相关 HDU1179-二分图最大匹配

Ollivanders: Makers of Fine Wands since 382 BC. Time Limit: 2000/1000 MS (Java/O

朱雀/ 2022年07月12日 05:03/ 0 赞/ 205 阅读

相关二分图和最大匹配

There are a group of students. Some of them may know each other, while others don't.

末蓝、/ 2022年06月08日 01:24/ 0 赞/ 206 阅读

相关【二分图匹配】棋盘游戏 HDU - 1281

Think: 1知识点：二分图匹配 2题意：在棋盘内选定一些位置，在这些位置中选取部分位置放置“车”，要求每一行或者每一列不能出现多余1个“车”，询问最多放置几个“车”

亦凉/ 2022年06月04日 00:29/ 0 赞/ 184 阅读

相关 HDU 1281& TOJ 2733 棋盘游戏二分图最大匹配

棋盘游戏 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

约定不等于承诺〃/ 2022年05月27日 00:46/ 0 赞/ 166 阅读

相关 [二分图]最大匹配

二分图的定义，以及判断图是否为二分图都很简单了。现在要说二分图的最大匹配。首先是定义吧，完美匹配就是一一对应，而最大匹配则是最大可以匹配的条数完美匹配一定是最大匹配

清疚/ 2021年11月23日 09:46/ 0 赞/ 277 阅读

相关 CH6801 棋盘覆盖（二分图最大匹配）

题意：给定一个 N\N 的棋盘，棋盘上有些位置不能防止任何东西，现用 1\2 的骨牌填充棋盘，问最多能铺多少块骨牌。分析：和骑士共存差不多的经典题，算是板子题，详见《

冷不防/ 2021年11月13日 23:34/ 0 赞/ 275 阅读