记录编号	177504	评测结果	AAAAAAAAAAAAAAAAA
题目名称	[USACO JAN05]泥泞的牧场	最终得分	100
用户昵称	一個人的雨	是否通过	通过
代码语言	C++	运行时间	0.051 s
提交时间	2015-08-12 10:33:41	内存使用	8.46 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn=5000;
const int maxm=1000;
int vis[maxn],girl[maxn];
int tim=0,n,m,ans=0,h=1,l=1;
vector<int>v[maxn];
char s[maxm][maxm];
int hang[maxm][maxm],lie[maxm][maxm];

bool find(int x){
	//vis[x]=tim;
	for (int i=0;i<v[x].size();++i)
	   if (vis[v[x][i]]!=tim){
		  vis[v[x][i]]=tim;
		  if (!girl[v[x][i]]||find(girl[v[x][i]])){
			  girl[v[x][i]]=x;
			  return 1;
		  }
	   }
	return 0;
}

int main()
{
	freopen("usaco_cover.in","r",stdin);
	freopen("usaco_cover.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=0;i<n;++i) {
		scanf("%s",&s[i]);
		for (int j=0;j<m;++j)
		   if (s[i][j]=='*'){
				while (s[i][j]=='*') hang[i][j++]=h;
				j--; h++;
		   }
	}
	for (int j=0;j<m;++j)
	   for (int i=0;i<n;++i)
		  if (s[i][j]=='*'){
				while (s[i][j]=='*') lie[i++][j]=l;
				i--; l++;
		  }
	for (int i=0;i<n;++i)
	   for (int j=0;j<m;++j)
		  if (s[i][j]=='*'){
				v[lie[i][j]].push_back(hang[i][j]);
				//v[hang[i][j]].push_back(lie[i][j]);
		  }
	for (int i=1;i<l;++i){
		++tim;
		if (find(i)) ans++;
	}
	printf("%d",ans);
	//system("pause");
}