题解：
sd的题目也真是奇怪
第一题有了最短路第二题还有
第二题有了网络流第三题还有
显然是可以网络流的
但考虑每个点只能存在一个这个条件
刚开始我以为是建分层图。。但发现这个时间复杂度太高了
其实我们考虑当两个人到一个点的时候可以交换速度（常用思想）
所以如果有解那么这个条件就是没有用的
所以也就是说这个条件是没有用的
那就变成了二分图最大权匹配
代码：
#include <bits/stdc++.h> #define N 40000 #define maxn 500000 using namespace std; struct re{ int a,b,c,from,flow,cost; }a[maxn]; struct ree{ int a,b,c; }e[maxn]; int l2,l,head[N],head2[N]; void arr(int x,int y,int z,int flow,int cost) { a[++l].a=head[x]; a[l].b=y; a[l].c=z; a[l].flow=flow; a[l].cost=cost; a[l].from=x; head[x]=l; } #define INF 1e9 int sum,d[N],s,t,p[N],aa[N],n,m; bool inq[N]; bool bellmanford(int &flow,int &cost) { for (int i=1;i<=sum;i++) d[i]=INF; memset(inq,0,sizeof(inq)); d[s]=0; inq[s]=1; aa[s]=INF; queue<int>q; q.push(s); while (!q.empty()) { int x=q.front(); q.pop(); int u=head[x]; while (u) { int v=a[u].b; if (a[u].c>a[u].flow&&d[v]>d[x]+a[u].cost) { d[v]=d[x]+a[u].cost; p[v]=u; aa[v]=min(aa[x],a[u].c-a[u].flow); if (!inq[v]) { q.push(v); inq[v]=1; } } u=a[u].a; } inq[x]=0; } if (d[t]==INF) return(0); flow+=aa[t]; cost+=d[t]*aa[t]; int x=t; while (x!=s) { int u=p[x]; a[u].flow+=aa[t]; if (u%2) a[u+1].flow-=aa[t]; else a[u-1].flow-=aa[t]; x=a[u].from; } return 1; } int flow,cost; void mincost() { while (bellmanford(flow,cost)); } int dx[5]={0,1,1,-1,-1}; int dy[5]={0,1,-1,1,-1}; queue<int> q; bool ff[1000][1000]; char cc[N]; int js(int x,int y) { return((x-1)*m+y); } bool pd(int x,int y) { if (x>=1&&x<=n&&y>=1&&y<=m&&!ff[x][y]) return(1); else return(0); } void arr2(int x,int y) { e[++l2].a=head2[x]; e[l2].b=y; head2[x]=l2; } int k,a1,b1; int x1[N],x2[N],y3[N],y4[N],dis[N]; bool vis[N]; int main() { freopen("noi.in","r",stdin); freopen("noi.out","w",stdout); std::ios::sync_with_stdio(false); cin>>n>>m>>k>>a1>>b1; for (int i=1;i<=n;i++) { cin>>cc; int len=strlen(cc); for (int j=0;j<len;j++) if (cc[j]=='*') ff[i][j+1]=1; } for (int i=1;i<=k;i++) cin>>x1[i]>>y3[i]; for (int i=1;i<=k;i++) cin>>x2[i]>>y4[i]; for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) if (pd(i,j)) { for (int i1=1;i1<=4;i1++) { if (pd(i+dx[i1]*a1,j+dy[i1]*b1)) { int k1=js(i,j); int k2=js(i+dx[i1]*a1,j+dy[i1]*b1); arr2(k1,k2); } if (pd(i+dx[i1]*b1,j+dy[i1]*a1)) { int k1=js(i,j); int k2=js(i+dx[i1]*b1,j+dy[i1]*a1); arr2(k1,k2); } } } sum=2*k+1; for (int i=1;i<=k;i++) { int ax1=js(x1[i],y3[i]); for (int j=1;j<=n*m;j++) dis[j]=INF; memset(vis,0,sizeof(vis)); dis[ax1]=0; q.push(ax1); vis[ax1]=1; while (!q.empty()) { int x2=q.front(); q.pop(); int u=head2[x2]; while (u) { int v=e[u].b; if (!vis[v]) { dis[v]=dis[x2]+1; q.push(v); vis[v]=1; } u=e[u].a; } } for (int j=1;j<=k;j++) { int ax2=js(x2[j],y4[j]); arr(i,j+k,1,0,dis[ax2]); arr(j+k,i,0,0,-dis[ax2]); } } s=0; t=2*k+1; for (int i=1;i<=k;i++) { arr(s,i,1,0,0); arr(i,s,0,0,0); arr(i+k,t,1,0,0); arr(t,i+k,0,0,0); } mincost(); cout<<cost; return 0; }