题目大意 :

给定一个 \(R \times C\) 的矩阵，其中有一些特殊的矩形，请问至少可以用任意长度，宽度为1矩形恰好覆盖。

必须平行与矩阵，且恰好覆盖。

---

前置知识 :

1.二分图最小点覆盖

---

思路 :

二分图最小点覆盖 ：每条边有2个端点，且二者至少选择一个，称之为“二要素”。

二分图最小点覆盖点数 \(=\) 二分图最大匹配边数

（出自算法竞赛进阶指南)

二分图与网络流学习 xht37

---

考虑一块1$\times$1的矩形，只能被横着的矩形，或者竖着的矩形覆盖，这就符合了“二要素”。 并且要使得覆盖的矩形最少，那么只需覆盖一次就好，这就符合了“二分图最小点覆盖”的特征。

如果就这样连边，跑匈牙利算法的话，是错的。

因为覆盖的是矩形，不可以覆盖到非特殊点，且同行或同列的矩形可以被同一块矩形覆盖到。那么，就可一贪心的想，对于一个1$\times\(1的特殊矩形\)(i,j)\(，如果与之同行且在它前面一个的矩形\)(i,j-1)\(，那么就可以与它连边，因为覆盖了\)(i,j-1)\(那么就覆盖了\)(i,j)$。列的话，同理。

---

定义 :

\(num1 , num2\)为行，列的当前编号。

\(cnt[i][j][0/1]\) 为 \((i,j)\)的行的编号与列的编号。

\(match[i]\) 为列 \(i\)的匹配行。

---

代码 :

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>

using namespace std;

const int kN=105;
const int kMax=5e3+5;

int r,c;
int to[kMax],nex[kMax],head[kMax],tot;
int match[kMax],ans;
int cnt[kN][kN][2];//(i,j)行的编号与列的编号
int num1,num2;//行的编号与列的编号

char a[kN][kN];

bool v[kMax];

void Add(int x,int y){to[++tot]=y;nex[tot]=head[x];head[x]=tot;}//链式前向星

bool Dfs(int x){//求二分图最大匹配边数 = 二分图最小点覆盖
	for(int i=head[x];i;i=nex[i]){
		int ar=to[i];
		if(v[ar]){continue;}
		v[ar]=1;
		if(!match[ar]||Dfs(match[ar])){
			match[ar]=x;return 1;
		}
	}
	return 0;
}

int main(){
	scanf("%d%d",&r,&c);
	for(int i=1;i<=r;++i){
		for(int j=1;j<=c;++j){
			cin>>a[i][j];
			if(a[i][j]=='*'){
				if(a[i][j-1]!='*'){cnt[i][j][0]=++num1;}//无法与相邻点在同一行覆盖
				else{cnt[i][j][0]=cnt[i][j-1][0];}//可以在同一行覆盖
				if(a[i-1][j]!='*'){cnt[i][j][1]=++num2;}//无法与相邻点在同一列覆盖
				else{cnt[i][j][1]=cnt[i-1][j][1];}//可以在同一列覆盖
				Add(cnt[i][j][0],cnt[i][j][1]);//建边
			}
		}
	}
	for(int i=1;i<=num1;++i){//以行为左部端点
		fill(v,v+kN,0);
		ans+=(Dfs(i));
	}
	printf("%d\n",ans);
	return 0;
}