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 linker[maxn], lx[maxn], ly[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;
            if(linker[y] == -1 || dfs(linker[y]))
            {
                linker[y] = x;
                return true;
            }
        }
        else if(stlck[y] > tmp)
        {
            stlck[y] = tmp;
        }
    }
    return false;
}
int km()
{
    memset(linker, -1, sizeof(linker));
    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++)
    {
        if(linker[i] != -1) {
            res += g[linker[i]][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;
}
时间: 08-15

POJ-2195的相关文章

POJ 2195 Going Home【最小费用流 二分图最优匹配】

题目大意:一个n*m的地图,上面有一些人man(m)和数量相等的house(H) 图上的距离为曼哈顿距离 问所有人住进一所房子(当然一个人住一间咯)距离之和最短是多少? 思路:一个人一间房,明显是二分图的模型,边权为人和房子的曼哈顿距离,然后算一下最小距离即可 懒得学KM了 最小费用流的经典建图 #include #include #include #include #include #define maxn 40000 #define inf 0x3f3f3f3f using namespac

POJ 2195 Going Home / HDU 1533(最小费用最大流模板)

题目大意: 有一个最大是100 * 100 的网格图,上面有 s 个 房子和人,人每移动一个格子花费1的代价,求最小代价让所有的人都进入一个房子.每个房子只能进入一个人. 算法讨论: 注意是KM 和 MCMF算法,我写的是MCMF算法,一开始想的是连10000个点,但是不会连那些大众点之间的边,只会连超级点和普通点之间的边.后来觉得只要连房子点和 人点就可以了.连从人到房子的边,容量是1,花费是他们之间的曼哈顿距离,然后超级源点和超级汇点像上面那样连接,注意连点的时候把他们每个点都具体化一下,就

poj 2195 Going Home 二分图最小权匹配KM算法

题意: 有n个人要回到n间房子里,每间房子只允许一个人,求n个人要走的最小距离和. 分析: 裸的二分图最小权匹配,KM搞之. 代码: //poj 2195 //sep9 #include <iostream> using namespace std; const int maxN=128; char g[maxN][maxN]; int mx[maxN],my[maxN],hx[maxN],hy[maxN]; int w[maxN][maxN]; int lx[maxN],ly[maxN],l

POJ 2195 Going Home (最小费用最大流)

题目链接:http://poj.org/problem?id=2195 题意:n*m的矩阵,地图上有若干个人(m)和房子(H),且人与房子的数量一致.man每移动一格费用为1,一个房子只能住一个人.现在要求所有的人出发,都入住房子,求最少话费. 思路:建立一个超级源点和汇点,源点与人相连费用为0,容量为1,人与房子相连,费用为人与房子的距离,容量为1,房子与汇点相连,费用为0,容量为1 #include <iostream> #include <cstdlib> #include

POJ 2195 Going Home(费用流)

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

POJ 2195 &amp; HDU 1533 Going Home(最小费用最大流)

题目链接: POJ:http://poj.org/problem?id=2195 HDU:http://acm.hdu.edu.cn/showproblem.php?pid=1533 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,

POJ 2195:Going Home(最小费用最大流)

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

poj 2195 最小费用最大流模板

/*Source Code Problem: 2195 User: HEU_daoguang Memory: 1172K Time: 94MS Language: G++ Result: Accepted Source Code */ #include <iostream> #include <stdio.h> #include <queue> #include <math.h> #include <string.h> using namespa

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

POJ 2195 Going Home

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 h