题解 P6062 【[USACO05JAN]Muddy Fields G】

此题重点在二分图的建图。 考虑放置木板的决策，由于可以重复覆盖，所以对于两个可以选择的区间 $a,b$，若 $b$ 被 $a$ 覆盖，那么选择 $a$ 一定优于选择 $b$。 解释如图：泥地为黄色，草地为绿色  显然，木板 $A$ 一定比木板 $B$ 更优，因为橙色部分可以重复覆盖。 由此易得所有的木板两头都是没有泥地的：若有，则增长此木板一定比原方案更优。 得到这个结论，我们可以先预处理出所有可能放置木板的位置，也就是在每行每列连续的泥地的位置。如图所示：所有木板可能放置的位置是下图的十个。  对于每一个点，要么被横着覆盖，要么被竖着覆盖。举例来讲，$(3,3)$ 在行上会被横木板 $3$ 覆盖，在列上会被竖木板 $4$ 覆盖。而我们要让所有的点都被覆盖，也就是需要满足下图所示的所有条件：  我们需要选出最少的木板满足这样的若干个约束条件。**我们把每一个泥地看成一条边，左端点为其对应的横木板，右端点为其对应的竖木板。** 显然这是一个二分图，左边全部为横木板，右边全部为竖木板。  考虑我们**放置一个木板**，相当于满足所有包含它的约束条件，**也就是将其所连的边进行染色**。 而对于每一个泥地（也就是边），**如果它被染色，就证明这个格子的约束条件已被满足**。 所以这个问题转化为：**一次操作可以选择一个点，将所连的边染色，目的是让所有边被染色。** 即为二分图最小点覆盖。 而最小点覆盖等于最大匹配，故建图跑匈牙利即可。 代码： ```cpp #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; } ```