POJ 2226 Muddy Fields（最小点覆盖）
来源：程序员人生 发布时间：2014-11-13 08:45:50 阅读次数：1878次
POJ 2226 Muddy Fields
题目链接
题意：给定1个图，要求用纸片去覆盖'*'的位置，纸片可以堆叠，但是不能放到'.'的位置，为最少需要几个纸片
思路：2分图匹配求最小点覆盖，和放车那题基本1样，就是注意要预处理1下行列，把连续横的'*'当做1行，竖的'*'当做1列，建图跑最小点覆盖便可
代码：
#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] == ⑴ || dfs(left[v])) {
left[v] = u;
return true;
}
}
return false;
}
int hungary() {
int ans = 0;
memset(left, ⑴, 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
", hungary());
}
return 0;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
