【题解】 P6062 [USACO05JAN]Muddy Fields G

· · 题解

【题解】 P6062 [USACO05JAN]Muddy Fields G

题意

有一个 n 行 m 列的矩形，其中的格子有两种类型，一种是草地，上面不能放木板；另一种是泥地，上面可以放木板。一个木板最长可以覆盖整行或整列，求最少的木板数。

解法

因为木板在一行或一列上可能不能完全覆盖，所以我们可以把整个图的行、列重新定义一下：在原图中，每一行连续的泥地标记为同一行，列同理，所以我们可以得到这样一张新的图：（以样例为例）

这部分可以这样处理：

    for (ri i = 1; i <= n; i++)
        for (ri j = 1; j <= m; j++) {
            if (s[i][j] == '.') continue;
            if (j == 1 || s[i][j - 1] == '.') cntx++;
            a[i][j].x = cntx;
        }
    for (ri j = 1; j <= m; j++)
        for (ri i = 1; i <= n; i++) {
            if (s[i][j] == '.') continue;
            if (i == 1 || s[i - 1][j] == '.') cnty++;
            a[i][j].y = cnty;
        }
// 要注意区分好行和列，不要弄混

要求的就是怎样用最少的木板覆盖整张图

我们可以对行和列连边建出一张图，因为行和列无关，所以其内部不会连边，即建出来的图一定是二分图。建好的图如图：

要令整张图被覆盖，就要让每块泥地都被覆盖。以第一张图 (1,1) 这个点为例：要么由第 1 块竖着的木板覆盖它，要么由第 1 块横着的木板覆盖它。换言之，这个点要么在左部，要么在右部，而且一定要关联一条边。用最小的木板数覆盖所有泥地，其实就等价于求出一个最小的点集，令每条边都至少有一个端点出现在这个点集中。

这不就是二分图最小点覆盖吗？

而由 Konig 定理可知：二分图最小点覆盖顶点数等于最大匹配

这样，问题就迎刃而解了：把每块泥地的行向列连边，求最大匹配即可

匈牙利应该在座都会吧

Code：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ri register int
const int N = 1010;
inline int read() {
    ri x = 0, f = 1;
    char ch = getchar();
    for (; !isdigit(ch); ch = getchar())
        if (ch == '-') f = -1;
    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
    return f * x;
}
struct Edge {
    int to, nxt;
} e[N << 1];
int head[N], cnt;
inline void add(int u, int v) {
    e[++cnt].to = v;
    e[cnt].nxt = head[u];
    head[u] = cnt;
}
int match[N];
bool vis[N];
bool dfs(int u) {
    for (ri i = head[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        if (vis[v]) continue;
        vis[v] = true;
        if (!match[v] || dfs(match[v])) {
            match[v] = u;
            return true;
        }
    }
    return false;
}
char s[N][N];
struct node {
    int x, y;
} a[N][N];
signed main() {
    int n = read(), m = read(), ans = 0;
    int cntx = 0, cnty = 0;
    for (ri i = 1; i <= n; i++) scanf("%s", s[i] + 1);
    for (ri i = 1; i <= n; i++)
        for (ri j = 1; j <= m; j++) {
            if (s[i][j] == '.') continue;
            if (j == 1 || s[i][j - 1] == '.') cntx++;
            a[i][j].x = cntx;
        }
    for (ri j = 1; j <= m; j++)
        for (ri i = 1; i <= n; i++) {
            if (s[i][j] == '.') continue;
            if (i == 1 || s[i - 1][j] == '.') cnty++;
            a[i][j].y = cnty;
        }
    for (ri i = 1; i <= n; i++)
        for (ri j = 1; j <= m; j++)
            if (s[i][j] == '*') add(a[i][j].x, a[i][j].y);
    // for (ri i = 1; i <= n; i++)
    //     for (ri j = 1; j <= m; j++)
    //         printf("i=%lld,j=%lld:x-%lld,y-%lld\n", i, j, a[i][j].x,
    //         a[i][j].y);
    for (ri i = 1; i <= cntx; i++) {
        memset(vis, false, sizeof(vis));
        ans += dfs(i);
    }
    cout << ans << endl;
    return 0;
}