-
前言
这题和[USACO05JAN]Muddy Fields G非常相似，唯一不同的就是这题覆盖的位置不能相互重叠。
学习了大佬隐隐约约妖艳的题解，自己做了一些补充。
-
分析
类似的，根据横/纵来构造二分图。
这题的突破点在砖块不能互相重叠，所以对于一个黑色格子，不能同时放 (2) 块 (1 imes x (x>1)) 的砖块。
如图：
正因为如此，放横的就不能放竖的，放竖的就不能放横的。此时一个二分图就成形了。如下图：
建好图后，要求的结果就可以转换了，道理类似前言的那题，最后要求的是最多选多少点，且这些点之间没有连边（保证结果最小）。
即独立集。
由引理得出结果，二分图的最大独立集 = 总点数-最大匹配数。
因为这题 (n,m le 200) ，直接跑二分图匹配复杂度似乎会到 (O(n^2m^2)) 。所以本题用网络流跑。
- 代码
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
using namespace std;
const int Maxn=8e4+5;
const int inf=1e9;
struct edge{
int v,nx,w;
}e[Maxn<<4];
int n,m,ne=-1,f[Maxn],deep[Maxn];
int cur[Maxn];
char str[205][205];
bool vis[Maxn];
queue<int> q;
void read(int u,int v,int w)
{
e[++ne].v=v;
e[ne].nx=f[u];
e[ne].w=w;
f[u]=ne;
}
bool bfs(int s,int t)
{
memset(deep,0x7f,sizeof(deep));
while(!q.empty())q.pop();
for(int i=0;i<=t;i++)cur[i]=f[i];
deep[s]=0;
q.push(s);
while(!q.empty())
{
int now=q.front();
q.pop();
for(int i=f[now];i!=-1;i=e[i].nx)
if(deep[e[i].v]>inf&&e[i].w)
{
deep[e[i].v]=deep[now]+1;
q.push(e[i].v);
}
}
if(deep[t]<inf)return 1;
return 0;
}
int dfs(int now,int t,int limit)
{
if(!limit||now==t)return limit;
int flow=0,x;
for(int i=cur[now];i!=-1;i=e[i].nx)
{
cur[now]=i;
if(deep[e[i].v]==deep[now]+1)
{
x=dfs(e[i].v,t,min(limit,e[i].w));
if(!x)continue;
flow+=x;
limit-=x;
e[i].w-=x;
e[i^1].w+=x;
if(!limit)break;
}
}
return flow;
}
int dinic(int s,int t)
{
int maxflow=0;
while(bfs(s,t))maxflow+=dfs(s,t,inf);
return maxflow;
}
int main()
{
int s,t,sum=0,cnt=0;
memset(f,-1,sizeof(f));
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%s",str[i]+1);
s=0,t=n*m*2+1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if(str[i][j]=='.')continue;
sum++;
int uu=(i-1)*m+j,rr=uu+n*m;// uu:id(i,j) rr:id(i,j)_
int vv=i*m+j,ll=rr-1;// vv:id(i+1,j) ll:id(i,j-1)_
if(str[i-1][j]=='#'&&!vis[uu])++cnt,vis[uu]++,read(s,uu,1),read(uu,s,0);
if(str[i][j-1]=='#'&&!vis[ll])++cnt,vis[ll]++,read(ll,t,1),read(t,ll,0);
if(str[i-1][j]=='#')
{
if(str[i][j+1]=='#')read(uu,rr,1),read(rr,uu,0);
if(str[i][j-1]=='#')read(uu,ll,1),read(ll,uu,0);
}
if(str[i+1][j]=='#')
{
if(str[i][j+1]=='#')read(vv,rr,1),read(rr,vv,0);
if(str[i][j-1]=='#')read(vv,ll,1),read(ll,vv,0);
}
}
printf("%d
",sum-(cnt-dinic(s,t)));
return 0;
}
[ ext{by Rainy7}
]