自动搬运

查看原文

来自洛谷，原作者为

	William2022 **

搬运于2025-08-24 23:02:45，当前版本为作者最后更新于2025-06-23 12:08:15，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

Going Home 题解

题目大意

在一个 $n\times m$ 的地图上，存在等量的人和房子，一个人走到一个房子的代价为他们的曼哈顿距离。
我们需要安排人与房子的对应关系，使得总代价最小。
$n,m\leq 100$

样例分析

HH..m 
..... 
.....
.....
mm..H

按照题目画出的图走就是最优方法。

$ans=10$

思考

注意到：

1. 每一个人都要找到房子，每一个房子都要找到人，是匹配问题
2. 匹配时候不同的对应关系有不同的代价

根据第一条，想到网络流进行匹配，考虑到第二条，应当使用费用流。

图论建模

人和房子是对应的，网络流建立如下：

1. 每个人作为源点，仅能流出 $1$ 的流量
2. 每个房子作为汇点，仅能接受 $1$ 的流量

而对于每个人都可以选择每个房子，所以对于每一个人，连接到每一个房子，费用为他们之间的曼哈顿距离。
跑最小费用最大流。

程序设计

1. 一个超级源点，对每一个人指向一条流量为 $1$，费用为 $0$ 的边
2. 一个超级汇点，所有房子对其指向一条流量为 $1$，费用为 $0$ 的边
3. 枚举每一个人，对每个房子指向一条费用为他们之间曼哈顿距离的边
4. 答案即为最大流的最小费用

代码

#include<bits/stdc++.h>
typedef long long ll;

const int E=25e6+10;
const int V=1e4+10;

int n,m;

struct pair{int x,y,id;};//这里的id指这个人或者房子在图中的编号
struct Star{int to,w,c,nxt;};
Star e[E*2];
int hd[V],star=1;

void addEdge(int u,int v,int w,int c){
	star++;
	e[star]={v,w,c,hd[u]};
	hd[u]=star;
}
void CostFlow(int u,int v,int w,int c){//建立流量边
	addEdge(u,v,w,c);
	addEdge(v,u,0,-c);
}

const int S=1,T=2;//超级源点，超级汇点
int cnt=2;//往后开点

int Distance(const pair &a,const pair &b){
	return abs(a.x-b.x)+abs(a.y-b.y);
}

int dis[V],pre[V];

bool SPFA(){
	std::bitset<V> in;
	std::queue<int> q;
	memset(dis,0x3f,sizeof(dis));
	
	q.push(S);
	dis[S]=0;
	in[S]=1;
	
	while(!q.empty()){
		int u=q.front();q.pop();
		in[u]=0;
		
		for(int id=hd[u];id;id=e[id].nxt){
			int v=e[id].to,w=e[id].w,c=e[id].c;
			if(!w)continue;
			
			if(dis[u]+c<dis[v]){
				pre[v]=id;
				dis[v]=dis[u]+c;
				if(!in[v]){
					q.push(v);
					in[v]=1;
				}
			}
		}
	}
	return (dis[T]<(int)(1e9));// 能否到达汇点
}
ll SSP(){//最小费用最大流 ssp
	ll ans=0;
	while(SPFA()){
		ans+=dis[T];
		for(int u=T;u!=S;u=e[pre[u]^1].to){
			e[pre[u]].w=0;
			e[pre[u]^1].w=1;
		}
	}
	return ans;
}

ll solve(){
	star=1;
	memset(hd,0,sizeof(hd));
	//输入
	std::vector<pair> H,M;//分别代表人和房子出现的位置
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			char c;
			std::cin>>c;
			if(c=='H')H.push_back({i,j,++cnt});
			else if(c=='m')M.push_back({i,j,++cnt});
		}
	}
	
	//图论建模
	for(pair p:H)CostFlow(S,p.id,1,0);
	for(pair p:M)CostFlow(p.id,T,1,0);
	
	for(pair a:H){
		for(pair b:M){
			CostFlow(a.id,b.id,1,Distance(a,b));
		}
	}
	//最小费用最大流
	
	return SSP();
}

signed main(){
	std::ios::sync_with_stdio(0);std::cout.tie(0);std::cin.tie(0);
	
	while(std::cin>>n>>m){
		if(!n)break;
		std::cout<<solve()<<"\n";
	}
}