题解 P2499 【[SDOI2012]象棋】

· · 题解

KM算法题解。

首先，“不能出现多颗棋子同时在某一格的情况”条件没有用，可以通过调整路径顺序避免这种情况。

考虑预处理所有起始点和目标点的距离，用BFS实现，应该都会吧。之后就是裸的二分图最小权匹配了，求出所有起始点到所有终点的最小权匹配，将边权取相反数直接跑KM即可，此处用BFS版KM保证时间复杂度。总时间复杂度为O(k^{3}+knm)，轻松AC。

#include<cstdio>
#include<cstring>
const int N=109,M=509;
char mp[N][N];
int d[N][N],qx[N*N],qy[N*N],n,m,k,a,b,sx[M],sy[M],tx[M],ty[M],lx[M],ly[M],sl[M],w[M][M],mt[M],p[M];
bool f[M];
int main(){
    register int i,j,l,x,y,u,v,h,t;
    scanf("%d%d%d%d%d",&n,&m,&k,&a,&b),memset(lx,-9,sizeof(lx));
    register int nx[9]={a,a,-a,-a,b,b,-b,-b},ny[9]={b,-b,b,-b,a,-a,a,-a};
    for(i=1;i<=n;++i)scanf("%s",mp[i]+1);
    for(i=1;i<=k;++i)scanf("%d%d",sx+i,sy+i);
    for(i=1;i<=k;++i)scanf("%d%d",tx+i,ty+i);
    for(i=1;i<=k;++i){
        h=0,t=1,qx[1]=sx[i],qy[1]=sy[i],memset(d,9,sizeof(d)),d[sx[i]][sy[i]]=0;
        while(h!=t){
            u=qx[++h],v=qy[h];
            for(j=0;j<8;++j){
                x=u+nx[j],y=v+ny[j];
                if(x>0&&y>0&&x<=n&&y<=m&&mp[x][y]=='.'&&d[x][y]>1e8)d[x][y]=d[u][v]+1,qx[++t]=x,qy[t]=y;
            }
        }
        for(j=1;j<=k;++j)w[i][j]=-d[tx[j]][ty[j]],lx[i]=lx[i]>w[i][j]?lx[i]:w[i][j];
    }//BFS预处理距离
    for(i=1;i<=k;++i){
        memset(sl,9,sizeof(sl)),memset(f,0,sizeof(f));
        for(mt[j=0]=i;mt[j];j=u){
            f[j]=1,l=1e8,x=mt[j];
            for(y=1;y<=k;++y)if(!f[y]){
                v=lx[x]+ly[y]-w[x][y];
                if(v<sl[y])sl[y]=v,p[y]=j;
                if(l>sl[y])l=sl[y],u=y;
            }
            for(y=0;y<=k;++y)if(f[y])lx[mt[y]]-=l,ly[y]+=l;else sl[y]-=l;
        }
        while(j)mt[j]=mt[p[j]],j=p[j];
    }//KM最小权匹配
    for(l=0,i=1;i<=k;++i)l-=lx[i]+ly[i];
    printf("%d",l);
    return 0;
}