题解：
二分+宽搜+KM
显然答案不能太大
然后二分一下
代码:
#include<bits/stdc++.h> const int N=115,M=1005; using namespace std; const int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1}; int m,n,cnt,pt,tot,c[N][N],d[N][N],x,y,t,path[N],bo[N],inq[N][N],mp[N][N]; struct node{int x,y;}a[N],b[N],h[N+5]; void bfs(int sx,int sy,int p) { memset(d,0x3f,sizeof(d)); d[sx][sy]=0; int i,t,head=0,tail=1; node u,v; h[1].x=sx;h[1].y=sy; memset(inq,0,sizeof(inq)); while (head!=tail) { head=head%M+1;u=h[head];inq[u.x][u.y]=0; for (int i=0;i<4;i++) { v.x=u.x+dx[i];v.y=u.y+dy[i]; if (v.x<=0||v.x>m||v.y<=0||v.y>n) continue; if (p^(d[u.x][u.y]&1)) if (c[v.x][v.y]<=c[u.x][u.y]) t=0;else t=1; else if (c[v.x][v.y]>=c[u.x][u.y]) t=0;else t=1; if (d[u.x][u.y]+t<d[v.x][v.y]) { d[v.x][v.y]=d[u.x][u.y]+t; if (!inq[v.x][v.y]){inq[v.x][v.y]=1;tail=tail%M+1;h[tail]=v;} } } } } int dfs(int x,int lim) { for (int i=1;i<=tot;i++) if (bo[i]&&mp[x][i]<=lim) { bo[i]=0; if (!path[i]||dfs(path[i],lim)) { path[i]=x; return 1; } } return 0; } int pd(int x) { int tmp=0; memset(path,0,sizeof(path)); for (int i=1;i<=(cnt<<1);i++) { memset(bo,1,sizeof(bo)); tmp+=(dfs(i,x)); } return tmp+x>=(cnt<<1); } int main() { scanf("%d%d%d%d",&m,&n,&cnt,&pt); for (int i=1;i<=(cnt<<1|1);i++)scanf("%d%d",&a[i].x,&a[i].y); for (int i=1;i<=pt;i++) { scanf("%d%d%d",&x,&y,&t); while (t--){b[++tot].x=x;b[tot].y=y;} } for (int i=1;i<=m;i++) for (int j=1;j<=n;j++)scanf("%d",&c[i][j]); for (int i=1;i<=(cnt<<1);i++) { if (i<=cnt) bfs(a[i].x,a[i].y,0); else bfs(a[i].x,a[i].y,1); for (int j=1;j<=tot;j++) mp[i][j]=d[b[j].x][b[j].y]; } int l=0,r=cnt<<1; while (l<r) { int mid=(l+r)>>1; if (pd(mid)) r=mid; else l=mid+1; } printf("%d ",l); return 0; }