题解 P6062 【[USACO05JAN]Muddy Fields G】

· · 题解

此题重点在二分图的建图。

考虑放置木板的决策，由于可以重复覆盖，所以对于两个可以选择的区间 a,b，若 b 被 a 覆盖，那么选择 a 一定优于选择 b。

解释如图：泥地为黄色，草地为绿色

显然，木板 A 一定比木板 B 更优，因为橙色部分可以重复覆盖。

由此易得所有的木板两头都是没有泥地的：若有，则增长此木板一定比原方案更优。

得到这个结论，我们可以先预处理出所有可能放置木板的位置，也就是在每行每列连续的泥地的位置。如图所示：所有木板可能放置的位置是下图的十个。

对于每一个点，要么被横着覆盖，要么被竖着覆盖。举例来讲，(3,3) 在行上会被横木板 3 覆盖，在列上会被竖木板 4 覆盖。而我们要让所有的点都被覆盖，也就是需要满足下图所示的所有条件：

我们需要选出最少的木板满足这样的若干个约束条件。我们把每一个泥地看成一条边，左端点为其对应的横木板，右端点为其对应的竖木板。 显然这是一个二分图，左边全部为横木板，右边全部为竖木板。

考虑我们放置一个木板，相当于满足所有包含它的约束条件，也就是将其所连的边进行染色。 而对于每一个泥地（也就是边），如果它被染色，就证明这个格子的约束条件已被满足。

所以这个问题转化为：一次操作可以选择一个点，将所连的边染色，目的是让所有边被染色。

即为二分图最小点覆盖。

而最小点覆盖等于最大匹配，故建图跑匈牙利即可。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m;
int cnt1,cnt2;
bool a[1002][1002];
int match[1002];
int ans;
bool visit[1002];
bool dfs(int x){
    for(int i=1;i<=cnt2;i++){
        if(a[x][i]&&!visit[i]){
            visit[i]=1;
            if(!match[i]||dfs(match[i])){
                match[i]=x;
                return 1;
            }
        }
    }
    return 0;
}
char ch[1002][1002];
int h[1002][1002];
int c[1002][1002];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){//统计横向木板 
        cin>>ch[i]+1;
        for(int j=1;j<=m;j++){
            if(ch[i][j]=='*'){
                if(j==1||ch[i][j-1]!='*'){
                    h[i][j]=++cnt1;
                }
                else h[i][j]=cnt1;
            }
        }
    }
    for(int i=1;i<=m;i++){//统计竖向木板 
        for(int j=1;j<=n;j++){
            if(ch[j][i]=='*'){
                if(j==1||ch[j-1][i]!='*'){
                    c[j][i]=++cnt2;
                }
                else c[j][i]=cnt2;
                a[h[j][i]][c[j][i]]=1;
            }
        }
    }
    for(int i=1;i<=cnt1;i++){//跑匈牙利 
        memset(visit,0,sizeof visit);
        ans+=dfs(i);
    }
    cout<<ans;
    return 0;
}