记录编号	552645	评测结果	AAAAAAWWAA
题目名称	[SDOI 2012]象棋	最终得分	80
用户昵称	瑆の時間~無盡輪迴·林蔭	是否通过	未通过
代码语言	C++	运行时间	1.923 s
提交时间	2020-08-01 23:15:56	内存使用	197.16 MiB

//EK-SPFA
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int N=12010;
int cost[N*1000],head[N],dis[N*1000],nxt[N*1000],to[N*1000];
//描述边
int TAG[N],vis[N],pre[N],far[N];//描述流图上的点
int tot=1,ans=0,S=N-2,T=N-1,n,m,k,a,b,a1,a2;
char mp[110][110];
void ADD(int x,int y,int diss,int costs)
{
	to[++tot]=y;
	cost[tot]=costs;
	dis[tot]=diss;
	nxt[tot]=head[x];
	head[x]=tot;
	to[++tot]=x;
	cost[tot]=-costs;
	dis[tot]=0;
	nxt[tot]=head[y];
	head[y]=tot;
}
bool SPFA()
{
	memset(far,0x3f3f3f3f,sizeof(far));
	memset(vis,0,sizeof(vis)); 
	queue<int> q;
	q.push(S);
	TAG[S]=0x3f3f3f3f;
	vis[S]=1;
	far[S]=0;
	while(q.size())
	{
		int x=q.front();
		q.pop();
		vis[x]=0;
		for(int i=head[x];i;i=nxt[i])
		{
			if(!dis[i])
				continue;//没流量了
			 if(far[to[i]]>far[x]+cost[i])
			 {
			 	far[to[i]]=far[x]+cost[i];
			 	pre[to[i]]=i;
			 	TAG[to[i]]=min(TAG[x],dis[i]);
				if(!vis[to[i]])
				{
					q.push(to[i]);
					vis[to[i]]=1; 
				} 
			 }
		}
	}
	if(far[T]==0x3f3f3f3f)
	{
		return 0;
	}
	return 1;
} 
void Update()
{
	int x=T;
	while(x!=S)
	{
		int i=pre[x];
		dis[i]-=TAG[T];
		dis[i^1]+=TAG[T];
		x=to[i^1];
	}
	ans+=TAG[T]*far[T];
}
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++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>mp[i][j];
		}
	}
	int A[4];
	int B[4];
	A[0]=a,A[1]=-a,A[2]=b,A[3]=-b;
	B[0]=b,B[1]=-b,B[2]=a,B[3]=-a;
	int X1,Y1;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			for(int S1=0;S1<=1;S1++)
			{
				for(int S2=2;S2<=3;S2++)
				{
					X1=i+A[S1];
					Y1=j+A[S2];
					if(mp[X1][Y1]=='*')
						continue;
					if(X1>=1&&X1<=n&&Y1>=1&&Y1<=m)
						ADD((i-1)*n+j,(X1-1)*n+Y1,0x3f3f3f3f,1);
				}
			}
			for(int S1=2;S1<=3;S1++)
			{
				for(int S2=0;S2<=1;S2++)
				{
					X1=i+A[S1];
					Y1=j+A[S2];
					if(mp[X1][Y1]=='*')
						continue;
					if(X1>=1&&X1<=n&&Y1>=1&&Y1<=m)
					{
						ADD((i-1)*n+j,(X1-1)*n+Y1,0x3f3f3f3f,1);
					}
						
				}
			}
		}
	}
	for(int i=1;i<=k;i++)
	{
		scanf("%d%d",&a1,&a2);
		ADD(S,(a1-1)*n+a2,1,0);
	}
	for(int i=1;i<=k;i++)
	{
		scanf("%d%d",&a1,&a2);
		ADD((a1-1)*n+a2,T,1,0);
	}
	while(SPFA())
	{
		Update();
	}
	printf("%d",ans);
	return 0;
}