POJ 2226 Muddy Fields(最小顶点覆盖)
最小 poj 覆盖 fields 顶点
2023-09-14 09:10:19 时间
POJ 2226 Muddy Fields
题意:给定一个图,要求用纸片去覆盖'*'的位置。纸片能够重叠。可是不能放到'.'的位置,为最少须要几个纸片
思路:二分图匹配求最小点覆盖。和放车那题基本一样。就是注意要预处理一下行列,把连续横的'*'当成一行,竖的'*'当成一列,建图跑最小点覆盖就可以
代码:
#include <cstdio> #include <cstring> #include <vector> #include <algorithm> using namespace std; const int N = 55; const int M = 1505; int n, m, tox[N][N], toy[N][N], xn, yn; char str[N][N]; vector<int> g[M]; int left[M], vis[M]; 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 < xn; i++) { memset(vis, 0, sizeof(vis)); if (dfs(i)) ans++; } return ans; } int main() { while (~scanf("%d%d", &n, &m)) { int cnt = 0; for (int i = 0; i < n; i++) { scanf("%s", str[i]); int flag = 0; for (int j = 0; j < m; j++) { if (str[i][j] == '*') { tox[i][j] = cnt; flag = 1; } else if (str[i][j] == '.' && flag) { g[cnt].clear(); cnt++; flag = 0; } } if (flag) { g[cnt].clear(); cnt++; } xn = cnt; } cnt = 0; for (int i = 0; i < m; i++) { int flag = 0; for (int j = 0; j < n; j++) { if (str[j][i] == '*') { toy[j][i] = cnt; flag = 1; } else if (str[j][i] == '.' && flag) { cnt++; flag = 0; } } if (flag) cnt++; yn = cnt; } for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (str[i][j] == '*') { g[tox[i][j]].push_back(toy[i][j]); } } } printf("%d\n", hungary()); } return 0; }
版权声明:本文博客原创文章,博客,未经同意,不得转载。
相关文章
- poj 2031Building a Space Station(几何判断+Kruskal最小生成树)
- poj 3101Astronomy(圆周追击+分数最小公倍数)
- Java实现 LeetCode 712 两个字符串的最小ASCII删除和(最长公共子串&&ASCII值最小)...
- Java实现 LeetCode 530 二叉搜索树的最小绝对差(遍历树)
- Java实现最小费用最大流问题
- 最大公约数和最小公倍数
- 【论文复现】—— 基于最小平方中值的点云平面拟合算法
- 二叉树的最小深度(C++)
- 偏最小二乘算法(PLS)回归建模 (Matlab代码实现)
- POJ 1548 Robots(最小路径覆盖)
- 最小相位系统
- 【华为OD机试 2023最新 】 组合出合法最小数(C++ 100%)
- 433. 最小基因变化 -深度优先遍历-力扣双百代码
- Python编程:web框架flask、web.py、tornado最小应用
- POJ 3041(最小点覆盖)
- POJ 3356 AGTC(最小编辑距离)