[USACO05JAN] Muddy Fields G
acwing指路
题目描述
大雨侵袭了奶牛们的牧场。
牧场是一个 $R \times C$ 的矩形,其中 $1 \leq R,C \leq 50$。大雨将没有长草的土地弄得泥泞不堪,可是小心的奶牛们不想在吃草的时候弄脏她们的蹄子。为了防止她们的蹄子被弄脏,约翰决定在泥泞的牧场里放置一些木板。每一块木板的宽度为 $1$ 个单位,长度任意,每一个板必须放置在平行于牧场的泥地里。
约翰想使用最少的木板覆盖所有的泥地.一个木板可以重叠在另一个木板上,但是不能放在草地上。
输入格式
第一行两个整数 $R,C$。
接下来 $R$ 行,每行 $C$ 个字符,描述牧场,其中 *
为泥地,.
为草地。
输出格式
输出一个整数,最少需要多少木板。
样例 #1
样例输入 #1
4 4
*.*.
.***
***.
..*.
样例输出 #1
4
最小点覆盖
- 对于木板, 如果合法 $1 \times a + 1$的木板 一定好于 $1 \times a$的木板, $a \times 1$木板同理
- 由此可以先给所有横纵方向的木板标号
- 对于每一个横着的木板一定有与其相交的竖着的木板
- 以每个木板为点,交点为边
- 要想覆盖所有的交点
- 则是在新建的二分图中用最少的点覆盖所有的边
- 即最小点覆盖问题
更详细的题解可以看这里
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
constexpr int N = 55, M = N * N;
int n, m;
struct Pos
{
bool mud;
int row, col;
}pos[N][N];
int h[M], e[M], ne[M], idx;
int match[M * 2];
bool st[M * 2];
void add(int a, int b)
{
e[++ idx] = b, ne[idx] = h[a], h[a] = idx;
}
bool find(int x)
{
if (st[x]) return false;
st[x] = true;
for (int i = h[x]; i; i = ne[i])
{
int j = e[i];
if (!match[j] || find(match[j]))
{
match[j] = x;
return true;
}
}
return false;
}
int main()
{
cin >> n >> m;
char s[N];
for (int i = 0; i < n; ++ i)
{
cin >> s;
for (int j = 0; j < m; ++ j)
pos[i][j].mud = s[j] == '*';
}
int rowSize = 0;
for (int row = 0; row < n; ++ row)
for (int col = 0; col < m; ++ col)
if (pos[row][col].mud)
if (col && pos[row][col - 1].mud)
pos[row][col].row = pos[row][col - 1].row;
else
pos[row][col].row = ++ rowSize;
int colSize = 0;
for (int col = 0; col < m; ++ col)
for (int row = 0; row < n; ++ row)
if (pos[row][col].mud)
if (row && pos[row - 1][col].mud)
pos[row][col].col = pos[row - 1][col].col;
else
pos[row][col].col = (++ colSize) + rowSize;
for (int i = 0; i < n; ++ i)
for (int j = 0; j < m; ++ j)
if (pos[i][j].mud)
add(pos[i][j].row, pos[i][j].col);
int res = 0;
for (int i = 1; i <= rowSize; ++ i)
{
memset(st, 0, sizeof st);
if (find(i))
++ res;
}
cout << res;
}
据说AcWing和洛谷有仇
hhh没听说过呀
y总说过
哪期视频,可以指个路吗
语法基础课里的视频,一个视频两三个小时,我后向也忘了,反正肯定是语法基础课里说的,别人问然后y总回答