自动搬运

查看原文

来自洛谷，原作者为

	Binary_Search_Tree 博客 https://cnblogs.com/bestlxm

搬运于2025-08-24 22:14:27，当前版本为作者最后更新于2020-01-09 22:37:19，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目传送门

这种匹配的问题一看就知道是网络流了吧qwq

因为$n$非常小。。。所以我们可以暴力枚举所有目标状态

然后从源点$S$向每一个初始节点连边权为$1$，费用为$0$的边

从每个目标节点向汇点$T$连一条边权为$1$，费用为$0$的边

对于每对$(i,j)$（$i$为第$i$个初始节点，$j$为第$j$个目标节点）

连一条边权为$1$，费用为最短路长度的边

最后跑最小费用最大流就可以了qwq

附上代码:

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#define INF 1000000000
#define M 10005
#define N 55
using namespace std;
int nxt[M],head[M],to[M],adj[M],cost[M],X[M],Y[M],XX[M],YY[M],nowX[M],nowY[M],dist[M],cur[M],F[N][N][N];
int mincost,tot,n,m,S,T,Ans=INF;
bool inq[M],vis[M],G[N][N];
int dx[10]={0,1,-1,0,0};
int dy[10]={0,0,0,1,-1};
int read(){//没什么用的快速读入
	int ans=0;char c=getchar();
	while (c<'0'||c>'9') c=getchar();
	while (c>='0'&&c<='9') ans=ans*10+c-'0',c=getchar();
	return ans;
}
void Write(int x){//没什么用的快速输出
	if (x<0) putchar('-'),x=-x;
	if (x<10) putchar(x^48);
	else Write(x/10),putchar((x%10)^48);
	return;
}
void add(int u,int v,int w,int Cost){
	nxt[tot]=head[u];head[u]=tot;to[tot]=v;adj[tot]=w;cost[tot]=Cost;tot++;
	nxt[tot]=head[v];head[v]=tot;to[tot]=u;adj[tot]=0;cost[tot]=-Cost;tot++;
	return;
}
bool SPFA(){
	for (register int i=S;i<=T;i++) dist[i]=INF,inq[i]=0;
	queue <int> Q;Q.push(T);inq[T]=1;dist[T]=0;
	while (!Q.empty()){
		int now=Q.front();Q.pop();inq[now]=0;
		for (register int i=head[now];~i;i=nxt[i])
			if (adj[i^1]>0&&dist[to[i]]>dist[now]-cost[i]){
				dist[to[i]]=dist[now]-cost[i];
				if (!inq[to[i]]) inq[to[i]]=1,Q.push(to[i]);
			}
	}
	return dist[S]<INF;
}
int dfs(int x,int low){
	vis[x]=1;if (x==T) return low;int used=0,a;
	for (register int &i=cur[x];~i;i=nxt[i])
		if (!vis[to[i]]&&adj[i]>0&&dist[to[i]]==dist[x]-cost[i]){
			a=dfs(to[i],min(low-used,adj[i]));
			if (a) adj[i]-=a,adj[i^1]+=a,mincost+=a*cost[i],used+=a;
			if (used==low) break;
		}
	return used;
}
int costflow(){
	int ans=0,a;
	while (SPFA()){
		vis[T]=1;
		while (vis[T]){
			for (register int i=S;i<=T;i++) cur[i]=head[i],vis[i]=0;
			while (a=dfs(S,INF)) ans+=a;
		}
	}
	return mincost;
}
int work(){
	memset(head,-1,sizeof(head));mincost=tot=0;//记得初始化
	for (register int i=1;i<=n;i++)
		if (G[nowX[i]][nowY[i]]) return INF;//判断目标状态是否合法
	for (register int i=1;i<=n;i++){
		add(S,i+1,1,0),add(i+n+1,T,1,0);
		for (register int j=1;j<=n;j++) add(i+1,j+n+1,1,F[i][nowX[j]][nowY[j]]);
	}
	return costflow();
}
void BFS(int x){//BFS找最短路
	queue <pair<int,int> > Q;
	for (register int i=1;i<=n;i++)
		for (register int j=1;j<=n;j++) F[x][i][j]=INF;
	F[x][X[x]][Y[x]]=0;Q.push(make_pair(X[x],Y[x]));
	while (!Q.empty()){
		pair <int,int> now=Q.front();Q.pop();
		for (register int i=1;i<=4;i++){
			int xx=now.first+dx[i],yy=now.second+dy[i];
			if (xx<1||xx>n||yy<1||yy>n||F[x][xx][yy]<INF||G[xx][yy]) continue;
			F[x][xx][yy]=F[x][now.first][now.second]+1;
			Q.push(make_pair(xx,yy));
		}
	}
	return;
}
int main(){
	n=read(),m=read();S=1,T=n+n+2;
	for (register int i=1;i<=n;i++) X[i]=read(),Y[i]=read();
	for (register int i=1,x,y;i<=m;i++) x=read(),y=read(),G[x][y]=1;
	for (register int i=1;i<=n;i++) BFS(i);
	for (register int i=1;i<=n;i++){
		for (register int j=1;j<=n;j++) nowX[j]=i,nowY[j]=j;
		Ans=min(Ans,work());
		for (register int j=1;j<=n;j++) nowX[j]=j,nowY[j]=i;
		Ans=min(Ans,work());
	}
	for (register int i=1;i<=n;i++) nowX[i]=nowY[i]=i;
	Ans=min(Ans,work());
	for (register int i=1;i<=n;i++) nowX[i]=i,nowY[i]=n+1-i;
	Ans=min(Ans,work());
	Write(Ans==INF?-1:Ans);//不要忘了输出-1
	return 0;
}

虽然代码长但不难写qwq

记得点赞啊