记录编号	369965	评测结果	AAAAAAAAAA
题目名称	[SDOI 2012]象棋	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.366 s
提交时间	2017-02-12 10:15:47	内存使用	9.09 MiB

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N=1010;
int n,m,k,a,b,sx[N],sy[N],ex[N],ey[N];
char s[N][N];
int dis[N][N],f[N][N];
int lx[N],ly[N],d[N];bool visx[N],visy[N];
queue<pair<int,int> > Q;
void bfs(int x){
	const int fx[8]={a,a,b,b,-a,-a,-b,-b};
	const int fy[8]={b,-b,a,-a,b,-b,a,-a};
	for (int i=1;i<=n;i++)
	for (int j=1;j<=m;j++)
		dis[i][j]=1e9;
	dis[sx[x]][sy[x]]=0;
	Q.push(make_pair(sx[x],sy[x]));
	while (!Q.empty()){
		int x=Q.front().first,y=Q.front().second;Q.pop();
		for (int k=0;k<8;k++){
			int a=x+fx[k],b=y+fy[k];
			if (a>0&&a<=n&&b>0&&b<=m&&dis[a][b]>dis[x][y]+1&&s[a][b]=='.')
				dis[a][b]=dis[x][y]+1,Q.push(make_pair(a,b));
		}
	}
	lx[x]=-1e9;
	for (int i=1;i<=k;i++)
		f[x][i]=-dis[ex[i]][ey[i]],lx[x]=max(lx[x],f[x][i]);
}
bool find(int x){
	if (visx[x]) return 0;
	visx[x]=1;
	for (int i=1;i<=k;i++)
	if (!visy[i]&&f[x][i]==lx[x]+ly[i]){
		visy[i]=1;
		if (!d[i]||find(d[i])){
			d[i]=x;return 1;
		}
	}
	return 0;
}
int main()
{
	freopen("chessc.in","r",stdin);
	freopen("chessc.out","w",stdout);
	scanf("%d%d%d%d%d",&n,&m,&k,&a,&b);
	for (int i=1;i<=n;i++) scanf("%s",s[i]+1);
	for (int i=1;i<=k;i++) scanf("%d%d",&sx[i],&sy[i]);
	for (int i=1;i<=k;i++) scanf("%d%d",&ex[i],&ey[i]);
	for (int i=1;i<=k;i++) bfs(i);
	for (int v=1;v<=k;v++)
	while (1){
		for (int i=1;i<=k;i++) visx[i]=visy[i]=0;
		if (find(v)) break;
		int d=1e9;
		for (int i=1;i<=k;i++) if (visx[i])
		for (int j=1;j<=k;j++) if (!visy[j])
			d=min(d,lx[i]+ly[j]-f[i][j]);
		for (int i=1;i<=k;i++){
			if (visx[i]) lx[i]-=d;
			if (visy[i]) ly[i]+=d;
		}
	}
	int ans=0;
	for (int i=1;i<=k;i++) ans-=f[d[i]][i];
	printf("%d\n",ans);
	return 0;
}