比赛 |
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;
}