二分图覆盖问题.
首先需要用宽度为1,长度任意的模板将泥地覆盖.
我们考虑每一个泥地,只有两个处理方式,要么是被一块横着的木板覆盖,要么是被一块竖着的木板覆盖.
那么我们考虑将横着的木板与竖着的木板分开建图,对于每一个泥地将所属的横木与竖木连边.
之后要求所有的泥地都要被覆盖,所以要选出最少的点将所有边覆盖.
只就是最小点覆盖.==最大匹配
#include<bits/stdc++.h> #define ll long long using namespace std; const int N=5010; int link[N],tot,n,m,id1[61][61],o,id2[61][61],vis[N],ans,match[N],p,hang; char c[61][61]; struct edge{int y,next;}a[N*1000]; vector<int>v1,v2; inline int read() { int x=0,ff=1; char ch=getchar(); while(!isdigit(ch)) {if(ch=='-') ff=-1;ch=getchar();} while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} return x*ff; } inline void add(int x,int y) { a[++tot].y=y; a[tot].next=link[x]; link[x]=tot; } inline bool dfs(int x) { for(int i=link[x];i;i=a[i].next) { int y=a[i].y; if(vis[y]!=p) { vis[y]=p; if(!match[y]||dfs(match[y])) {match[y]=x;return true;} } } return false; } int main() { // freopen("1.in","r",stdin); n=read();m=read(); for(int i=1;i<=n;++i) scanf("%s",c[i]+1); for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) { if(c[i][j]=='.') continue; int k=j;++o; while(k<=m&&c[i][k]=='*') id1[i][k]=o,++k; j=k; } hang=o; for(int i=1;i<=m;++i) for(int j=1;j<=n;++j) { if(c[j][i]=='.') continue; int k=j;++o; while(k<=n&&c[k][i]=='*') id2[k][i]=o,++k; j=k; } for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) if(c[i][j]=='*') add(id1[i][j],id2[i][j]); for(int i=1;i<=hang;++i) { ++p; if(dfs(i)) ans++; } printf("%d",ans); return 0; }
我敢保证这绝对是我打的最ugly的代码了(没有之一)
同时也祝自己AcWing上一百道题了！！！