POJ2226 Muddy Fields（最小顶点覆盖）

亦凉 2021-11-09 23:58 263阅读 0赞

## 题意：在一个n\*m的草地上，.代表草地，\*代表水，现在要用宽度为1，长度不限的木板盖住水，木板可以重叠，但是所有的草地都不能被木板覆盖。问至少需要的木板数。 ##

## 分析：“2要素”经典题，详见《算法竞赛进阶指南》P429。 ##

## 代码： ##

#include <cstdio>
    #include <vector>
    #include <cstring>
    #include <iostream>
    using namespace std;
    const int N = 56;
    int n, m, tot = 1, a[N][N][2], f[N*N], ans;
    char s[N][N];
    bool 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] || dfs(f[y])) {
    			f[y] = x;
    			return 1;
    		}
    	}
    	return 0;
    }
    
    int main() {
    	cin >> n >> m;
    	for (int i = 1; i <= n; i++) scanf("%s", s[i] + 1);
    	for (int i = 1; i <= n; i++)
    		for (int j = 1; j <= m + 1; j++)
    			if (s[i][j] == '*') a[i][j][0] = tot;
    			else ++tot;
    	int t = tot;
    	for (int j = 1; j <= m; j++)
    		for (int i = 1; i <= n + 1; i++)
    			if (s[i][j] == '*') a[i][j][1] = tot;
    			else ++tot;
    	for (int i = 1; i <= n; i++)
    		for (int j = 1; j <= m; j++)
    			if (s[i][j] == '*') {
    				e[a[i][j][0]].push_back(a[i][j][1]);
    				e[a[i][j][1]].push_back(a[i][j][0]);
    			}
    	for (int i = 1; i < t; i++) {
    		memset(v, 0, sizeof(v));
    		ans += dfs(i);
    	}
    	cout << ans << endl;
    	return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关 Python实现最小顶点覆盖算法——Minimum Vertex Cover

Python实现最小顶点覆盖算法——Minimum Vertex Cover 最小顶点覆盖( Minimum Vertex Cover)是一个重要的图论问题，其目的是在保持边

「爱情、让人受尽委屈。」/ 2024年03月17日 17:20/ 0 赞/ 39 阅读

相关 poj 题目3041 Asteroids （最小点覆盖）

[http://poj.org/problem?id=3041][http_poj.org_problem_id_3041] 最小覆盖：最小覆盖要求用最少的点（Ｘ集合

不念不忘少年蓝@/ 2022年12月22日 02:25/ 0 赞/ 142 阅读

相关 POJ3020 最小边覆盖（匈牙利算法）

题目链接： [POJ3020][] 题目大意：在一个网格中，给定特殊点的位置，问你最少需要多少个信号塔（只能上下左右选择其中一个分析覆盖两个特殊点）才能覆盖所有的特殊点。

不念不忘少年蓝@/ 2022年05月17日 11:41/ 0 赞/ 175 阅读

相关 POJ 2226 Muddy Fields 题解《挑战程序设计竞赛》

[为什么80%的码农都做不了架构师？>>> ][80_] ![hot3.png][] ![POJ 2226 Muddy Fields 题解《挑战程序设计竞赛》][POJ

野性酷女/ 2022年01月15日 10:41/ 0 赞/ 217 阅读

相关 poj2594 （最小路径覆盖 + floyd）

题目链接 [http://poj.org/problem?id=2594][http_poj.org_problem_id_2594]) 题目大意：一个有向图中，有若干

迷南。/ 2022年01月10日 05:41/ 0 赞/ 192 阅读

相关 HDU1054Strategic Game(最小顶点覆盖数)

我们来先了解一下什么是最小顶点覆盖；图G的顶点覆盖是一个顶点集合V，使得G中的每一条边都接触V中的至少一个顶点。我们称集合V覆盖了G的边。最小顶点覆盖是用最少的顶点来

小鱼儿/ 2021年12月14日 00:33/ 0 赞/ 210 阅读

相关 poj 2226 还是最小点覆盖的匹配问题

这题比3041要有点难度，主要是在判断节点的时候，要两次扫描输入的矩阵。这个叫我shi也想不到啊。。人家discuss里面给了很好的模板，学着点吧。具体的分析请看下面:

左手的ㄟ右手/ 2021年11月29日 17:42/ 0 赞/ 230 阅读

相关 Poj 3041 Asteroids + Poj 2226 Muddy Fields(二分图与一类选方格题目)

Poj 3041 Asteroids 思路：把方阵看做一个特殊的二分图（以行列分别作为两个顶点集V1、V2，其中| V1|=| V2|）然后把每行x或者每列y看成一个点

秒速五厘米/ 2021年11月22日 21:01/ 0 赞/ 248 阅读

相关 POJ2226 Muddy Fields（最小顶点覆盖）

题意：在一个n\m的草地上，.代表草地，\代表水，现在要用宽度为1，长度不限的木板盖住水，木板可以重叠，但是所有的草地都不能被木板覆盖。问至少需要的木板数。分析：“2

亦凉/ 2021年11月09日 23:58/ 0 赞/ 264 阅读

相关 poj 3041 匈牙利算法最小点覆盖

题意：一个N \ N的矩阵，每个格子有些行星，有种特殊武器，一次能消灭一行，或一列，问最少使用多少次这样得武器，可以消灭所有行星。构图：刚开始的思路是最少的边覆盖所

ゝ一纸荒年。/ 2021年11月02日 14:24/ 0 赞/ 280 阅读