POJ-2195

Going Home

 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 19680 Accepted: 10003

Description

On a grid map there are n little men and n houses. In each unit time, every little man can move one unit step, either horizontally, or vertically, to an adjacent point. For each little man, you need to pay a \$1 travel fee for every step he moves, until he enters a house. The task is complicated with the restriction that each house can accommodate only one little man.

Your task is to compute the minimum amount of money you need to pay in order to send these n little men into those n different houses. The input is a map of the scenario, a ‘.‘ means an empty space, an ‘H‘ represents a house on that point, and am ‘m‘ indicates there is a little man on that point. You can think of each point on the grid map as a quite large square, so it can hold n little men at the same time; also, it is okay if a little man steps on a grid with a house without entering that house.

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
.m
H.
5 5
HH..m
.....
.....
.....
mm..H
7 8
...H....
...H....
...H....
mmmHmmmm
...H....
...H....
...H....
0 0
```

Sample Output

```2
10
28
```

Source

Pacific Northwest 2004

```/**
题意:相同数目的人和房子 n个人分不同的房子,然后走的每一步1￥ 问最小的花费
做法：km(二分图最大权匹配)
**/
#include <iostream>
#include <cmath>
#include <algorithm>
#include <string.h>
#include <stdio.h>
using namespace std;
const int maxn = 110;
const int INF = 0x3f3f3f3f;
int g[maxn][maxn];
int stlck[maxn];
bool visx[maxn], visy[maxn];
int nx, ny;
bool dfs(int x)
{
visx[x] = true;
for(int y = 0; y < ny; y++)
{
if(visy[y] == true) {
continue;
}
int tmp = lx[x] + ly[y] - g[x][y];
if(tmp == 0)
{
visy[y] = true;
{
return true;
}
}
else if(stlck[y] > tmp)
{
stlck[y] = tmp;
}
}
return false;
}
int km()
{
memset(ly, 0, sizeof(ly));
for(int i = 0; i < nx; i++)
{
lx[i] = -INF;
for(int j = 0; j < ny; j++)
{
if(g[i][j] > lx[i]) {
lx[i] = g[i][j];
}
}
}
for(int x = 0; x < nx; x++)
{
for(int i = 0; i < ny; i++)
{
stlck[i] = INF;
}
while(true)
{
memset(visx, false, sizeof(visx));
memset(visy, false, sizeof(visy));
if(dfs(x)) {
break;
}
int d = INF;
for(int i = 0; i < ny; i++)
if(!visy[i] && d > stlck[i]) {
d = stlck[i];
}
for(int i = 0; i < nx; i++)
if(visx[i]) {
lx[i] -= d;
}
for(int i = 0; i < ny; i++)
{   if(visy[i]) {
ly[i] += d;
}
else {
stlck[i] -= d;
}
}
}
}
int res = 0;
for(int i = 0; i < ny; i++)
{
}
}
return res;
}
char ch[maxn];
struct Node
{
int x;
int y;
Node() {}
Node(int _x, int _y) {
x = _x;
y = _y;
}
} node_m[maxn], node_h[maxn];
int dist(Node a, Node b)
{
return abs(a.x - b.x) + abs(a.y - b.y);
}
int main()
{
int n, m;
while(~scanf("%d %d", &n, &m))
{
if(n == 0 && m == 0) {
break;
}
nx = 0;
ny = 0;
for(int i = 0; i < n; i++)
{
scanf("%s", ch);
for(int j = 0; j < m; j++)
{
if(ch[j] == ‘m‘)
{
node_m[nx].x = i;
node_m[nx].y = j;
nx++;
}
else if(ch[j] == ‘H‘)
{
node_h[ny].x = i;
node_h[ny].y = j;
ny++;
}
}
}
memset(g, 0, sizeof(g));
for(int i = 0; i < nx; i++)
{
for(int j = 0; j < ny; j++)
{
g[i][j] = -1 * dist(node_m[i], node_h[j]);
}
}
int res = km();
printf("%d\n", abs(res));
}
return 0;
}```

POJ 2195 Going Home / HDU 1533（最小费用最大流模板） POJ 2195 Going Home（费用流）

http://poj.org/problem?id=2195 题意: 在一个网格地图上,有n个小人和n栋房子.在每个时间单位内,每个小人可以往水平方向或垂直方向上移动一步,走到相邻的方格中.对每个小人,每走一步需要支付1美元,直到他走入到一栋房子里.每栋房子只能容纳一个小人. 计算出让n个小人移动到n个不同的房子需要支付的最小费用. 思路: 源点和每个人相连,容量为1,费用为0. 汇点和每栋房子相连,容量为1,费用为0. 每个人和每栋房子相连,容量为1,费用为人和房子之间的距离. 这样一来,跑一

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

http://poj.org/problem?id=2195 题意:有一个地图里面有N个人和N个家,每走一格的花费是1,问让这N个人分别到这N个家的最小花费是多少. 思路:通过这个题目学了最小费用最大流.最小费用最大流是保证在流量最大的情况下,使得费用最小. 建图是把S->人->家->T这些边弄上形成一个网络,边的容量是1(因为一个人只能和一个家匹配),边的费用是曼哈顿距离,反向边的费用是-cost. 算法的思想大概是通过SPFA找增广路径,并且找的时候费用是可以松弛的.当找到这样一条增

POJ - 2195 Going Home（最小费用最大流） 1.N*M的矩阵中,有k个人和k个房子,每个人分别进入一个房子中,求所有人移动的最小距离. 2.人看成源点,房子看成汇点,求最小费用最大流. 建图-- 人指向房子,容量为1,费用为人到房子的曼哈顿距离. 建立超级源点和超级汇点:超级源点指向人,容量为1,费用为0:超级汇点指向房子,容量为1,费用为0. 求超级源点到超级汇点的最小费用最大流即可. ps:容量为什么都设为1?---有待研究.. 3. 1.Bellman-Ford: #include<iostream> #include<st