比赛 20160309 评测结果 AAAAAAAAAA
题目名称 象棋 最终得分 100
用户昵称 Satoshi 运行时间 0.460 s
代码语言 C++ 内存使用 21.75 MiB
提交时间 2016-03-09 21:31:36
显示代码纯文本
#include <fstream>
#include <algorithm>
#include <queue>
#define N 1010
using namespace std;
ifstream in("chessc.in");
ofstream out("chessc.out");
int X,Y,n,m,xx,yy;
char op;
bool zhang[N][N]={0};
bool l[N][N]={0};
int f[N][N]={0};
int w[2*N][2*N]={0};
int INF=(1<<28),inf=5000;
int dir[4][2]={{1,1},{1,-1},{-1,1},{-1,-1}};
int slack[2*N]={0};
int match[2*N]={0};
int lable[2*N]={0};
bool vis[2*N]={0};
class point
{
public:
	int x,y;
	void make(int a,int b)
	{
		x=a;
		y=b;
	}
	void print()
	{
		out<<x<<' '<<y<<endl;
	}
}A[N],B[N];
point operator +(point a,point b)
{
	point c;
	c.x=a.x+b.x;
	c.y=a.y+b.y;
	return c;
}
bool legal(point a)
{
	int i;
	if(a.x>=1&&a.x<=X&&a.y>=1&&a.y<=Y)
	{
		if(!zhang[a.x][a.y])return 1;
	}
	return 0;
}
void SPFA(point s)
{
	int i,j,sum=0;
	point u,v;
	queue<point > q;
	for(i=1;i<=X;i++)for(j=1;j<=Y;j++)l[i][j]=0;
	for(i=1;i<=X;i++)for(j=1;j<=Y;j++)f[i][j]=INF;
	f[s.x][s.y]=0;
	q.push(s);
	while(!q.empty())
	{
		u=q.front();
		q.pop();
		l[u.x][u.y]=1;
		//sum++;
		//u.print();
		for(i=0;i<=3;i++)
		{
			v.x=u.x+dir[i][0]*xx;
			v.y=u.y+dir[i][1]*yy;
			if(legal(v))
			{
				if(!l[v.x][v.y])
				{
					l[v.x][v.y]=1;
					f[v.x][v.y]=f[u.x][u.y]+1;
					q.push(v);
				}
			}
		}
		for(i=0;i<=3;i++)
		{
			v.x=u.x+dir[i][0]*yy;
			v.y=u.y+dir[i][1]*xx;
			if(legal(v))
			{
				if(!l[v.x][v.y])
				{
					l[v.x][v.y]=1;
					f[v.x][v.y]=f[u.x][u.y]+1;
					q.push(v);
				}
			}
		}
	}
	//out<<sum<<endl;
	//out<<sum<<endl;
}
void read()
{
	int i,j;
	in>>X>>Y>>n>>xx>>yy;
	for(i=1;i<=X;i++)
	{
		for(j=1;j<=Y;j++)
		{
			in>>op;
			if(op=='*')zhang[i][j]=1;
		}
	}
	for(i=1;i<=n;i++)in>>A[i].x>>A[i].y;
	for(i=1;i<=n;i++)in>>B[i].x>>B[i].y;
	m=n;
	for(i=1;i<=n;i++)
	{
		for(j=n+1;j<=n+m;j++)
		{
			w[i][j]=w[j][i]=inf-INF;
		}
	}
	for(i=1;i<=n;i++)
	{
		SPFA(A[i]);
		for(j=1;j<=n;j++)
		{
			w[i][n+j]=w[n+j][i]=inf-f[B[j].x][B[j].y];
		}
	}
	
	/*for(i=1;i<=n;i++)
	{
		for(j=n+1;j<=n+m;j++)
		{
			//A[i].print();
			//B[j].print();
			out<<w[i][j]<<endl;
			//out<<endl;
		}
		out<<endl;
	}*/
}
bool find(int u)
{
	int i,t;
	vis[u]=1;
	for(i=n+1;i<=n+m;i++)
	{
		if(vis[i]||!w[u][i])continue;
		t=lable[u]+lable[i]-w[u][i];
		if(!t)
		{
			vis[i]=1;
			if(match[i]==-1||find(match[i]))
			{
				match[i]=u;
				return 1;
			}
		}
		else slack[i]=min(slack[i],t);
	}
	return 0;
}
void KM()
{
	int i,j,k;
	int d=0;
	for(i=1;i<=n+m;i++)match[i]=-1;
	for(i=1;i<=n;i++)
	{
		lable[i]=-INF;
		for(j=n+1;j<=n+m;j++)
		{
			lable[i]=max(lable[i],w[i][j]);
		}
	}
	for(i=1;i<=n;i++)
	{
		while(true)
		{
			for(j=1;j<=n+m;j++)vis[j]=0;
			for(j=n+1;j<=n+m;j++)slack[j]=INF;
			if(find(i))break;
			d=INF;
			for(j=n+1;j<=n+m;j++)if(!vis[j])d=min(d,slack[j]);
			for(j=1;j<=n;j++)if(vis[j])lable[j]-=d;
			for(j=n+1;j<=n+m;j++)if(vis[j])lable[j]+=d;
		}
	}
}
void work()
{
	int i;
	int ans=0;
	KM();
	for(i=n+1;i<=n+m;i++)
	{
		if(match[i]!=-1)ans=ans+(inf-w[match[i]][i]);
	}
	out<<ans<<endl;
	/*for(i=1;i<=n;i++)
	{
		
	}*/
}
int main()
{
	read();
	work();
	return 0;
}