Link:

Solution:

很容易通过解可行性的单调性想到二分答案，接下来考虑如何验证解

 

发现一个很奇妙的条件：步兵和骑兵的个数相同

因此交换位置时不用考虑可行性，保证能完成交换（口胡证明一下就行了）

 

于是可以将每一次交换位置想成转变职业（不用考虑能否交换）

每一个士兵先用$bfs$预处理其到每个格子需要的转变次数。

对于一次$check(mid)$，由于上述性质，$交换次数<=mid$的移动都是合法的

只要先跑一遍$交换次数<=mid$的士兵和位置的最大匹配$Max_{Match}$

再考虑$Max_{Match}+mid>=2*K$是否成立即可（多出的贡献$mid$是对于“天兵”的特殊处理）

 

Code:

#include 
     
      using namespace std;typedef pair
      
        P;#define X first#define Y secondconst int MAXN=1e3+10;int dx[]={
   0,0,1,-1},dy[]={
   1,-1,0,0};P dat[MAXN],ly[MAXN];int N,M,K,T,h[MAXN][MAXN],tot=0;int match[MAXN],dist[MAXN][MAXN],w[MAXN][MAXN];bool vis[MAXN];void bfs(int st_x,int st_y,int f){    queue
       
 que;que.push(P(st_x,st_y));    memset(dist,0x3f,sizeof(dist));dist[st_x][st_y]=0;    while(!que.empty())    {        P t=que.front();que.pop();        for(int i=0;i<4;i++)        {            int fx=t.X+dx[i],fy=t.Y+dy[i],delta;            if(fx<1 || fx>N || fy<1 || fy>M) continue;            if(f^(dist[t.X][t.Y]&1))                if(h[fx][fy]<=h[t.X][t.Y]) delta=0; else delta=1;            else                if(h[fx][fy]>=h[t.X][t.Y]) delta=0; else delta=1;            if(dist[fx][fy]>dist[t.X][t.Y]+delta)            {                dist[fx][fy]=dist[t.X][t.Y]+delta;                que.push(P(fx,fy));            }        }    }}bool dfs(int u,int lim){    for(int i=1;i<=tot;i++)        if(!vis[i] && w[u][i]<=lim)        {            vis[i]=true;            if(match[i]==-1 || dfs(match[i],lim))            {                match[i]=u;                return true;            }        }    return false;}bool check(int x){    memset(match,-1,sizeof(match));    int ret=0;    for(int i=1;i<=2*K;i++)    {        memset(vis,0,sizeof(vis));        if(dfs(i,x)) ret++;    }    return (ret+x)>=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",&dat[i].X,&dat[i].Y);    for(int i=1;i<=T;i++)    {        int x,y,z;scanf("%d%d%d",&x,&y,&z);        while(z--) ly[++tot]=P(x,y);    }    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++) //bfs预处理    {        if(i<=K) bfs(dat[i].X,dat[i].Y,0);        else bfs(dat[i].X,dat[i].Y,1);        for(int j=1;j<=tot;j++) w[i][j]=dist[ly[j].X][ly[j].Y];    }        int l=0,r=K*2; //二分答案    while(l<=r)    {        int mid=(l+r)>>1;        if(check(mid)) r=mid-1;        else l=mid+1;    }    printf("%d",l);    return 0;}
      
     

 

Review:

此题的难点在于将 交换位置$->$转变职业

还是要注意题目中的特殊性质（EX：两职业个数相同），看看能不能推出一些奇妙的结论