记录编号	271445	评测结果	AAAAAAAAAAAAAAAAA
题目名称	[USACO JAN05]泥泞的牧场	最终得分	100
用户昵称	Hzoi_	是否通过	通过
代码语言	C++	运行时间	0.005 s
提交时间	2016-06-16 06:37:05	内存使用	0.39 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=60;
struct edge{
	int to;
	edge *prev;
}ee[maxn*maxn];
void insert(int,int);
bool path(int);
int maxmatch();
char getfchar();
int len=0;
edge *last[maxn*maxn]={NULL};
int na,nb,ca[maxn*maxn],cb[maxn*maxn];
bool vis[maxn*maxn];
int id[maxn][maxn][2]={{{0}}};
int n,m,k;
char a[maxn][maxn];
int main(){
#define MINE
#ifdef MINE
	freopen("usaco_cover.in","r",stdin);
	freopen("usaco_cover.out","w",stdout);
#endif
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)a[i][j]=getfchar();
	k=0;
	for(int i=1;i<=n;i++){
		k++;
		for(int j=1;j<=m;j++){
			if(a[i][j]=='.'){
				while(j<=m&&a[i][j]=='.')j++;
				if(j<=m)k++;
			}
			id[i][j][0]=k;
		}
	}
	na=k;
	k=0;
	for(int j=1;j<=m;j++){
		k++;
		for(int i=1;i<=n;i++){
			if(a[i][j]=='.'){
				while(i<=n&&a[i][j]=='.')i++;
				if(i<=n)k++;
			}
			id[i][j][1]=k;
		}
	}
	nb=k;
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(a[i][j]=='*')
		insert(id[i][j][0],id[i][j][1]);
	printf("%d",maxmatch());
	return 0;
}
void insert(int x,int y){
	ee[len].to=y;
	ee[len].prev=last[x];
	last[x]=&ee[len++];
}
bool path(int x){
	for(edge *e=last[x];e;e=e->prev){
		int y=e->to;
		if(!vis[y]){
			vis[y]=true;
			if(!cb[y]||path(cb[y])){
				ca[x]=y;
				cb[y]=x;
				return true;
			}
		}
	}
	return false;
}
int maxmatch(){
	int result=0;
	for(int i=1;i<=na;i++)if(!ca[i]){
		memset(vis,0,sizeof(vis));
		result+=path(i);
	}
	return result;
}
inline char getfchar(){
	char c=getchar();
	while(c!='*'&&c!='.')c=getchar();
	return c;
}