记录编号	271047	评测结果	AAAAAAAAAA
题目名称	[ZOJ 1654]放置机器人	最终得分	100
用户昵称	Go灬Fire	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2016-06-15 16:16:06	内存使用	19.92 MiB

//目的：求最小点覆盖，即使用最少的点覆盖所有的边 
//每一横排的连通块作为X集合。每一纵排的连通块作为Y集合
//对X   Y进行hungary 
#include<cmath>
#include<stdio.h>
#include<algorithm>
#include<cstring>
using namespace std;
#define maxn 1100
struct Edge{
	int next,to;
}e[maxn*maxn];
struct Node{
	int stand,cross;//a[x][y].stand   :点（x，y）属于纵向联通块 a[x][y].stand
					// a[x][y].cross   :点（x，y）属于横向联通块 a[x][y].cross 
}a[maxn][maxn];
int cx[maxn],cy[maxn],len=0,h,z,n,m,head[maxn];//h:横，z:纵, n:横联通块数，m：纵联通块数
//cx【】：X集合    cy【】：Y集合           
char s[maxn][maxn];
bool Visit[maxn]; 
void Init();
void Insert(int,int);
int path(int);
void hungary();
void Bfs_cross();//横向搜索求联通块 
void Bfs_stand();//纵向搜索求联通块 
int main(){
	freopen("placetherobots.in","r",stdin);
	freopen("placetherobots.out","w",stdout); 
	Init();
	return 0;
}
void Init(){
	memset(head,-1,sizeof(head));
	scanf("%d%d",&h,&z);
	for(int i=1;i<=h;i++){
		for(int j=1;j<=z;j++){
			scanf(" %c ",&s[i][j]);
		}
	}
	Bfs_cross();Bfs_stand();
	for(int i=1;i<=h;i++){
		for(int j=1;j<=z;j++){
			if(a[i][j].cross && a[i][j].stand && s[i][j]=='o'){
				Insert(a[i][j].cross,a[i][j].stand);//使用邻接表
				//原因：邻接矩阵不会写 
			}
		}
	}
	hungary();
}
void Bfs_cross(){
	for(int i=1;i<=h;i++){
		int j=1;
		while(j<=z){
			if((s[i][j]=='o' || s[i][j]=='*')&& (j==1 || s[i][j-1]=='#')){
				n++;
				while(s[i][j]=='o' || s[i][j]=='*'){
					a[i][j].cross=n;
					j++;
				}
			}
			j++;
		}
	}
}
void Bfs_stand(){
	for(int i=1;i<=z;i++){
		int j=1;
		while(j<=h){
			if((s[j][i]=='*' || s[j][i]=='o') && (j==1 || s[j-1][i]=='#')){
				m++;
				while(s[j][i]=='o' || s[j][i]=='*'){
					a[j][i].stand=m;
					j++;
				}
			}
			j++;
		}
	}
}
void Insert(int x,int y){
	len++;
	e[len].to=y;
	e[len].next=head[x];
	head[x]=len;
}
void hungary(){
	int ans=0;
	for(int i=1;i<=n;i++){
		if(cx[i]==0){
			memset(Visit,0,sizeof(Visit));
			ans+=path(i);
		}
	}
	printf("%d\n",ans);
}
int path(int x){
	for(int i=head[x];i!=-1;i=e[i].next){
		int j=e[i].to;
		if(Visit[j]==0){
			Visit[j]=1;
			if(!cy[j] || (path(cy[j]))){
				cx[x]=j;cy[j]=x;
				return 1;
			}
		}
	}
	return 0;
}