自动搬运

查看原文

来自洛谷，原作者为

	panyf **

搬运于2025-08-24 21:38:22，当前版本为作者最后更新于2020-01-28 13:15:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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;
}