Muddy Fields G

希望能比其他题解更让人理解一点。 蓝色/白色的点都是非泥坑点。绿色的点是泥坑点。

捕捉要素建模

首先，作为一个稍微见识过一些转图论的题目的OIer，你应该先想到这是图论题。

我们捕捉到题目中发现有要覆盖所有泥地，珂以猜出是个覆盖问题或SAT问题（当然这是面对此题夭折的算法）。然后被覆盖的对象应该是泥坑。然后发现数据范围较小，于是珂以把对象具体为每个小泥坑。

泥坑作为点

我们先看泥坑作为点。

从上图我们珂以看到，一个点要么被一个纵向木板覆盖，要么被一个横向木板覆盖，由于模板一盖肯定是盖满整个泥坑块，所以就是一定要选择自己处于的最长纵向泥坑块和自己处于的最长横向泥坑块其中的一个。好像2-SAT问题啊。

是的你没错，这就是2-SAT —— 等等题目要求的是最少放多少……再见了2-SAT。

想法夭折。

泥坑作为边

我们把带有每个泥坑的纵连通块和横连通块的图放出来。

根据前面的经验，这无非就是把一个泥坑块想象成一条边，所在的横向和纵向泥坑块是点，遇到一个泥坑点就把横向泥坑块所对应的点和纵向泥坑块所对应的点连起来。

整理一下，点是每一个横/纵向泥坑连通块作为一个点，然后每一个小泥坑作为边连接两个点，求最小点覆盖。

由于这是一个二分图（纵连通块不能连纵连通块，横连通块也不能连横连通块），所以珂以用 König 定理转换为二分图做。

二分图的最小点覆盖数= 二分图的最大匹配数。

所以转换边后这就是二分图匹配。

算法分解

首先我们要找横连通块，遍历每一个行，然后用while去找横连通块

纵连通块同上

然后遍历每一个泥坑，去建边。建好边后跑一个 Dinic 或者 Hungary 去做二分图即可。二分图就不多讲了

代码

#include<bits/stdc++.h>
using namespace std;
const int N=109,M=109*109*2;
int n,m; char c[N][N]; int cnt1,cnt2,h[N][N],l[N][N],ans;
struct edge{int to,nxt;}e[M]; int hd[M],tot;		//申明变量没啥好说的 
void add(int u,int v){
	e[++tot]=(edge){v,hd[u]}; hd[u]=tot;
}
bool vst[M*2]; int cc[M*2];
bool hungary(int u){								//匈牙利（用dinic也行 
	for(int i=hd[u],v;i;i=e[i].nxt)
		if(!vst[v=e[i].to])
			if(cc[v]==(!(vst[v]=1))||hungary(cc[v]))
				return cc[v]=u,1;
	return 0; 
}
int main(){
	scanf("%d%d",&n,&m);
	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]=='*') ++cnt1;    //新的连通块 
			while(c[i][j]=='*') h[i][j++]=cnt1; //横向连通块 
		}
	}
	for(int j=1;j<=m;j++){
		for(int i=1;i<=n;i++){
			if(c[i][j]=='*') ++cnt2;	//新的连通块 
			while(c[i][j]=='*') l[i++][j]=cnt2,l[i-1][j]+=cnt1; //纵向连通块 
		}
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(c[i][j]=='*') add(h[i][j],l[i][j]),add(l[i][j],h[i][j]); //建边 
	for(int i=1;i<=cnt1;i++) memset(vst,0,sizeof(vst)),ans+=hungary(i);
	printf("%d",ans);
	return 0;
}