题目连接

感觉这题思路比较像 P2402，但是稍微复杂一些。

做法

首先我们假设没有天兵的情况。

不难想到，超能力是在每个兵都不能移动时使用，这样显然不劣。

其次，一定是骑兵与步兵互相交换。

于是可以先预处理出对于每个兵 $K_i$ 到目标格子 $T_j$，记为 $dis_{i,j}$。

然后，再二分超能力的使用次数，记为 $mid$。

这里进行建模：

  1. 源点向每个兵建一条边，容量为 $1$。

  2. 每个目标格子向汇点建一条边，容量为 $R_i$。

  3. $\forall dis_{i,j}\le mid$，兵 $K_i$ 向 目标格子 $T_j$，建一条边，容量为 $1$。

在上图中跑最大流，记为 $cnt$，当 $cnt\ge2\times K$ 答案既合法。

这时再来讨论有天兵的情况。

首先天兵可以干什么？可以在使用超能力的时候把兵放到目标格子去。可以放多少个？可以放 $mid$ 个。所以最后的判断改成 $mid+cnt\ge2\times K$ 即可。

实现

稍微说一下预处理 $dis$。

我是用的 SPFA，但是据说可以用 01bfs。

首先是对每个点都跑一边 SPFA。

对于当前到底是骑兵还是步兵可以用当前步数的奇偶性来判断。

代码

#include<cstring>
#include<iostream>
#include<queue>
#define pii pair<int,int>
#define mp(x,y) make_pair(x,y)
using namespace std;
struct sss
{
    int q,w,e,nxt;
}a[1000005];
int cnt,head[1000005],d[1000005],n,now[1000005],m,N,S,T;
using namespace std;
queue<int>q;
void adde(int q,int w,int e)
{
    a[++cnt].q=q;
    a[cnt].w=w;
    a[cnt].e=e;
    a[cnt].nxt=head[q];
    head[q]=cnt;
    a[++cnt].q=w;
    a[cnt].w=q;
    a[cnt].e=0;
    a[cnt].nxt=head[w];
    head[w]=cnt;
}
bool bfs()
{
    memset(d,0,sizeof(d));
    while(q.size())q.pop();
    q.push(S);
    d[S]=1;
    now[S]=head[S];
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        for(int i=head[x];i;i=a[i].nxt)
        {
            if(a[i].e&&!d[a[i].w])
            {
                q.push(a[i].w);
                now[a[i].w]=head[a[i].w];
                d[a[i].w]=d[x]+1;
                if(a[i].w==T)return 1;
            }
        }
    }
    return 0;
}
int dinic(int x,int flow)
{
    if(x==T)return flow;
    int rest=flow;
    for(int i=now[x];i&&rest;i=a[i].nxt)
    {
        now[x]=i;
        if(a[i].e&&d[a[i].w]==d[x]+1)
        {
            int k=dinic(a[i].w,min(rest,a[i].e));
            if(!k)d[a[i].w]=0;
            a[i].e-=k;
            a[i%2?i+1:i-1].e+=k;
            rest-=k;
        }
    }
    return flow-rest;
}
//                    Dinci                    //
int dis[105][105],vis[105][105],h[105][105],t,K;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
bool check(pii x)
{
    if(x.first<1||x.first>n||x.second<1||x.second>m)return 0;
    return 1;
}
void SPFA(int sx,int sy,int d)
{
    queue<pair<int,int>>q;
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    vis[sx][sy]=1;
    dis[sx][sy]=0;
    q.push(mp(sx,sy));
    while(!q.empty())
    {
        pii x=q.front();
        q.pop();
        vis[x.first][x.second]=0;
        for(int i=0;i<4;i++)
        {
            pii y=mp(x.first+dx[i],x.second+dy[i]);
            if(!check(y))continue;
            int w=0,p=(dis[x.first][x.second]&1)^d;//0b1q
            if(h[y.first][y.second]<h[x.first][x.second]&&!p)w=1;
            if(h[y.first][y.second]>h[x.first][x.second]&&p)w=1;
             if(dis[y.first][y.second]>dis[x.first][x.second]+w)
             {
                dis[y.first][y.second]=dis[x.first][x.second]+w;
                if(!vis[y.first][y.second])q.push(y),vis[y.first][y.second]=1;
            }
        }
    }
}
//                    SPFA                     //
int pos[10005][2],tar[10005][3],Dis[1005][1005];
bool check(int mid)
{
    cnt=0;
    memset(head,0,sizeof(head));
    for(int i=1;i<=2*K;i++)adde(S,i,1);
    for(int i=1;i<=t;i++)adde(i+2*K,T,tar[i][2]);
    for(int i=1;i<=2*K;i++)
    {
        for(int j=1;j<=t;j++)
        {
            if(Dis[i][j]<=mid)adde(i,j+2*K,1);
        }
    }
    int ans=0,flow=0;
    while(bfs())while(flow=dinic(S,1e9))ans+=flow;
    return ans+mid>=2*K;
}
int main()
{
    scanf("%d%d%d%d",&n,&m,&K,&t);
    for(int i=1;i<=2*K+1;i++)scanf("%d%d",&pos[i][0],&pos[i][1]);
    for(int i=1;i<=t;i++)scanf("%d%d%d",&tar[i][0],&tar[i][1],&tar[i][2]);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)scanf("%d",&h[i][j]);
    }
    for(int i=1;i<=2*K;i++)
    {
        SPFA(pos[i][0],pos[i][1],i>K);
        for(int j=1;j<=t;j++)Dis[i][j]=dis[tar[j][0]][tar[j][1]];
    }
    S=2*K+t+1;
    T=2*K+t+2;
    int l=0,r=2*K,ans;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(check(mid))
        {
            r=mid-1;
            ans=mid;
        }
        else l=mid+1;
    }
    printf("%d",ans);
}