POJ 2226 Muddy Fields（最小點覆蓋）
來源：程序員人生 發布時間：2014-11-13 08:45:50 閱讀次數：2003次
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;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
