题目来源：2018冬令营模拟测试赛（十）
题解：
继续鬼畜网络流……
首先这题有个显然的做法：bfs预处理出每个起点到每个终点的最短步数，然后直接建边加超级源汇跑费用流即可；
但是这样边数是$n^2$的，时间复杂度正好能过但是很卡常，要写EK才能过；
显然我是不会EK的，所以有一种更优秀的建图方法：
直接在原图点上建边，如果两个点能一步走到就连费用为1，流量为inf的边，建超级源建费用为0，流量为1的边连向所有起点，所有终点同样连向超级汇，直接跑费用流即可……
正确性显然，但是我不是很理解为什么这样会更快……
顺便学习了一波zkw费用流（多路增广是什么？不存在的）
代码：
1 #include<algorithm>
2 #include<iostream>
3 #include<cstring>
4 #include<cstdio>
5 #include<cmath>
6 #include<queue>
7 #define inf 2147483647
8 #define eps 1e-9
9 #define get(x,y) ((x-1)*n+y)
10 using namespace std;
11 typedef long long ll;
12 struct edge{
13 int v,w,z,next;
14 }a[200001];
15 int way[8][2];
16 int n,m,N,aa,b,x,y,cnt=0,vs,vt,tot=1,tt=0,cst=0,flow=0,ans=0,head[100001],nm[201][201];
17 char mp[201][201];
18 bool vis[100001];
19 void add(int u,int v,int w,int z){
20 a[++tot].v=v;
21 a[tot].w=w;
22 a[tot].z=z;
23 a[tot].next=head[u];
24 head[u]=tot;
25 a[++tot].v=u;
26 a[tot].w=0;
27 a[tot].z=-z;
28 a[tot].next=head[v];
29 head[v]=tot;
30 }
31 int aug(int u,int x){
32 if(u==vt){
33 ans+=cst*x;
34 return x;
35 }
36 int mxf=x;
37 vis[u]=true;
38 for(int tmp=head[u];tmp!=-1;tmp=a[tmp].next){
39 int v=a[tmp].v;
40 if(a[tmp].w&&!a[tmp].z&&!vis[v]){
41 int f=aug(v,min(x,a[tmp].w));
42 a[tmp].w-=f;
43 a[tmp^1].w+=f;
44 mxf-=f;
45 if(!mxf)return x;
46 }
47 }
48 return x-mxf;
49 }
50 bool lab(){
51 int mi=inf;
52 for(int i=vs;i<=vt;i++){
53 if(vis[i]){
54 for(int tmp=head[i];tmp!=-1;tmp=a[tmp].next){
55 int v=a[tmp].v;
56 if(a[tmp].w&&!vis[v]){
57 mi=min(mi,a[tmp].z);
58 }
59 }
60 }
61 }
62 if(mi==inf)return false;
63 for(int i=vs;i<=vt;i++){
64 if(vis[i]){
65 for(int tmp=head[i];tmp!=-1;tmp=a[tmp].next){
66 a[tmp].z-=mi;
67 a[tmp^1].z+=mi;
68 }
69 }
70 }
71 cst+=mi;
72 return true;
73 }
74 int main(){
75 memset(head,-1,sizeof(head));
76 scanf("%d%d%d%d%d",&n,&m,&N,&aa,&b);
77 vs=0,vt=n*m+1;
78 way[0][0]=aa,way[0][1]=b;
79 way[1][0]=aa,way[1][1]=-b;
80 way[2][0]=-aa,way[2][1]=b;
81 way[3][0]=-aa,way[3][1]=-b;
82 way[4][0]=b,way[4][1]=aa;
83 way[5][0]=b,way[5][1]=-aa;
84 way[6][0]=-b,way[6][1]=aa;
85 way[7][0]=-b,way[7][1]=-aa;
86 for(int i=1;i<=n;i++){
87 scanf("%s",mp[i]+1);
88 for(int j=1;j<=m;j++)nm[i][j]=++cnt;
89 }
90 for(int i=1;i<=N;i++){
91 scanf("%d%d",&x,&y);
92 add(vs,nm[x][y],1,0);
93 }
94 for(int i=1;i<=N;i++){
95 scanf("%d%d",&x,&y);
96 add(nm[x][y],vt,1,0);
97 }
98 for(int i=1;i<=n;i++){
99 for(int j=1;j<=m;j++){
100 if(mp[i][j]=='.'){
101 for(int k=0;k<8;k++){
102 int ii=i+way[k][0],jj=j+way[k][1];
103 if(ii&&jj&&ii<=n&&jj<=m&&mp[ii][jj]=='.')add(nm[i][j],nm[ii][jj],inf,1);
104 }
105 }
106 }
107 }
108 do{
109 do{
110 flow+=tt;
111 memset(vis,0,sizeof(vis));
112 }while(tt=aug(vs,inf));
113 }while(lab());
114 printf("%d",flow<N?-1:ans);
115 return 0;
116 }