记录编号	238917	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]部落战争	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.043 s
提交时间	2016-03-19 15:27:31	内存使用	2.28 MiB

#include<cstdio>
#include<iostream>
#include<vector>
#include<deque>
using namespace std;
const int SIZEN=60,SIZEM=6000,INF=0x7fffffff/2;
int N,M;
char c[SIZEN][SIZEN];
int id[SIZEN][SIZEN]={0};
int tot=0;
vector<int> s[SIZEM];
int R,C;
int dx[]={1,1},dy[]={-1,1};
class miku
{
public:
	int fr,to,cap,flow;
	miku(){}
	miku(int a,int b,int c,int d)
	{
		fr=a,to=b,cap=c,flow=d;
	}
}E[SIZEM*20];
int S,T;
void read()
{
	scanf("%d%d%d%d",&N,&M,&R,&C);
	S=0;
	for(int i=0;i<N;i++) scanf("%s",c[i]);
	for(int i=0;i<N;i++)
	{
		for(int j=0;j<M;j++) id[i][j]=++tot;
	}
}
bool on(int x,int y)
{
	if(x<0||y<0) return 0;
	if(x>=N||y>=M) return 0;
	if(c[x][y]=='x') return 0;
	return 1;
}
int totw=0;
void add(int fr,int to,int cap)
{
	s[fr].push_back(totw);E[totw++]=miku(fr,to,cap,0);
	s[to].push_back(totw);E[totw++]=miku(to,fr,0,0);
}
deque<int> Q;
int ans=0;
int H[SIZEM]={0},e[SIZEM]={0};
void push(int x,int t)
{
	miku &v=E[t];
	int flow=min(e[x],v.cap-v.flow);
	e[x]-=flow;v.flow+=flow;
	e[v.to]+=flow;E[t^1].flow-=flow;
	if(v.to!=S&&v.to!=T&&e[v.to]) Q.push_back(v.to);
}
void use_up(int x)
{
	int mi;
	while(e[x])
	{
		mi=INF;
		for(int i=0;i<s[x].size();i++)
		{
			miku &v=E[s[x][i]];
			if(v.cap<=v.flow) continue;
			if(H[v.to]==H[x]-1)
			{
				push(x,s[x][i]);
				if(!e[x]) break;
			}
			else mi=min(mi,H[v.to]);
		}
		if(!e[x]) break;
		H[x]=mi+1;
	}
}
void maxflow()
{
	H[0]=T;if(H[0]>100) H[0]=100;
	e[0]=INF;
	for(int i=0;i<s[0].size();i++) push(0,s[0][i]);
	while(!Q.empty())
	{
		int x=Q.front();
		//cout<<x<<endl;
		Q.pop_front();
		use_up(x);
	}
	ans-=e[T];
	printf("%d\n",ans);
}
void makegragh()
{
	S=0;T=2*tot+1;
	//cout<<T<<endl;
	for(int i=0;i<N;i++)
	{
		for(int j=0;j<M;j++)
		{
			if(c[i][j]=='x') continue;
			//cout<<c[i][j]<<endl;
			add(S,id[i][j],1);
			//add(id[i][j],id[i][j]+tot,1);
			add(id[i][j]+tot,T,1);
			ans++;
			for(int k=0;k<2;k++)
			{
				int x=i+dx[k]*R,y=j+dy[k]*C;
				if(on(x,y)) add(id[i][j],id[x][y]+tot,1);
			}
			if(R==C) continue;
			for(int k=0;k<2;k++)
			{
				int x=i+dx[k]*C,y=j+dy[k]*R;
				if(on(x,y)) add(id[i][j],id[x][y]+tot,1);
			}
		}
	}
}
int main()
{
	freopen("lanzerb.in","r",stdin);
	freopen("lanzerb.out","w",stdout);
	read();
	makegragh();
	//cout<<"arrive"<<endl;
	maxflow();
	return 0;
}