POJ 2195 Going Home （最小费用最大流）

POJ 2195 Going Home （最小费用最大流）

Description

Input

There are one or more test cases in the input. Each case starts with a line giving two integers N and M, where N is the number of rows of the map, and M is the number of columns. The rest of the input will be N lines describing the map. You may assume both N and M are between 2 and 100, inclusive. There will be the same number of ‘H’s and ‘m’s on the map; and there will be at most 100 houses. Input will terminate with 0 0 for N and M.

Output

For each test case, output one line with the single integer, which is the minimum amount, in dollars, you need to pay.

Sample Input

2 2.mH.5 5HH..m...............mm..H7 8...H.......H.......H....mmmHmmmm...H.......H.......H....0 0

Sample Output

21028

题意

给出一张地图， ​​.​​​ 是空地， ​​H​​​ 是房子， ​​m​​ 是小人，并且地图上有相同数量的房子与小人，每个小人每次只能横向或者纵向移动一格，求最终所有人都找到一间独立的房子所走的步数。

思路

幸好地图上没有墙（降低难度），人物也可以相遇在同一格，那么小人距离任意一个房间的步数便是它们两者横坐标差+纵坐标差。

找一个源点，它与所有小人之见都有一条容量为1费用为0的边，然后所有房子与汇点之间也有一条容量为1费用为0的边，小人与房子之间的边容量为1，费用为它们之间的距离（步数）。

当然反向建图也可以，因为这张图是对称的嘛！并且房子个数与小人个数也相等。

然后求从源点到汇点之间的最小费用即可。

AC 代码

#include#include#include#include#include#includeusing namespace std;#include#include

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。