- POJ 2195 - Going Home
- Time: 1000MS
- Memory: 65536K
- 难度: 中级
- 分类: 费用流
0x00 POJ 原题
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
0x10 题目概述
给定一个 N*M 的地图,地图上有若干个 man 和 house,且 man 与 house 的数量一致。man 每移动一格需花费 $1(即单位费用=单位距离),一间 house 只能入住一个 man。现在要求所有的 man 都入住 house,求最小费用。
0x20 解题思路
费用流问题。
构图:
把 man 作为一个顶点集合 U,house 作为另一个顶点集合 V,把 U 中所有点到 V 中所有点连线,费用 cost[u][v]为abs(△x)+abs(△y),反向弧费用 cost[v][u]= -cost[u][v],容量 cap[u][v]=1,构成一个多源多汇的二分图。
由于每一个多源多汇的网络流都必有一个与之对应的单源单汇的网络流,为了便于解题,由此构造一个超级源 s 和超级汇 t,超级源 s 与 U 中所有点相连,费用 cost[s][u]=0(这是显然的),容量 cap[s][u]=1;V 中所有点与超级汇 t 相连,费用 cost[v][t]=0(这是显然的),容量 cap[t][v]=1。
至于其他不连通的点,费用与容量均为 0。容量为 0 的边,可以理解为饱和边,不再连通。而上述的所有边之所以容量初始化为 1,是因为每间 house 只允许入住 1 个 man。而与超级源(汇)相连的边的费用之所以为 0,是为了现在所构造的单源单汇网络流最终所求的最小费用等于原来的多源多汇网络流的最小费用。
求解:
接下来的解题方法有关“最小费用最大流”,请未知的同学先去看看相关文献。
其实题目所求的最小费用,就是最短距离。用 spfa 算法求上述二分图 G 的最短路径,该最短路径就是图 G 的所有增广链中费用最小的一条。比较该增广链上所有边的容量,最小的容量就是“可分配的最大流 MaxFlow”。
再者就是利用 MaxFlow 对增广链上的各条边的容量进行调整,正向弧容量减去 MaxFlow,反向弧容量加上 MaxFlow。然后该条增广链上各条边的费用分别乘以 MaxFlow 之和,就是第一个 man 到达合适的 house 所花费的最小费用。而图 G 经过调整,变成图 G1。
针对图 G1 再次使用 spfa 算法,找到第二条增广链…..重复上述算法,直到无法找到增广链为止,则得到的费用和就是所求。
此种解题方法是先计算最小费用,然后再在保证费用最小的情况下,增大流量,最终达到求解目的。理论上,对于有 n 个 man 的图,可以找到 n 条增广链,即重复迭代 spfa 算法 n 次。若超过 n 次,则说明该图存在负权环,无解。但本题并无输出“无解”的要求,故可认为测试数据中不存在此类数据,因此在循环 spfa 算法时,不必计算次数,用 while() 足矣。
最后要注意的是:
Discuss 上很多人说用了栈空间定义的数组,提交会 RE 或 TLE,数组开大之后才能 AC,因此便怪罪于测试数据有误。
其实不然。真正的原因是,题目所提及的 N 与 M 纯粹是地图的行数和列数,与 man 或 house 的个数无关,而我看了他们的代码,有部分同学却误以为 N 就是 man 的个数,导致出现 RE。
因此在此强调一下,题目的 N 不等于 man 的个数,建议大家先对地图的 man 个数进行数数,得到 man 的个数,然后再开堆空间(new 函数);而非要开栈空间的同学也未尝不可,由于 N 与 M 的值均 <=100,且 man 与 house 的个数一致,则认为 man 的个数上限为 100*100/2=5000。
0x30 测试数据
0x40 AC 源码
//Memory Time
//612K 63MS
#include<iostream>
#include<memory.h>
#include<cmath>
#include<queue>
using namespace std;
struct coordinate
{
int x,y;
};
class solve
{
public:
solve(int row,int col):R(row),C(col)
{
MinCost=0;
n=0;
Input();
StructureBinaryMap();
pre=new int[2*n+2];
memset(pre,0,sizeof(int)*(2*n+2));
dist=new int[2*n+2];
vist=new bool[2*n+2];
while(spfa())
AddMaxFlow();
}
~solve()
{
cout<<MinCost<<endl;
delete[] m;
delete[] H;
delete[] dist;
delete[] vist;
for(int i=0;i<R;i++)
delete[] InMap[i];
for(int j=0;j<2*n+2;j++)
{
delete[] cost[j];
delete[] cap[j];
}
}
int inf() const{return 0x7FFFFFFF;}
int min(int a,int b) {return a<b?a:b;}
void Input(void);
void StructureBinaryMap(void); //构造二分图
bool spfa(void); //搜索从超级源到超级汇的最短路(即最小费用)的增广链
void AddMaxFlow(void); //增广链调整(曾流),计算最小费用
protected:
int R,C; //地图尺寸R*C ,
int n; //the number of man or Houses
int s,t; //s:超级源编号,t:超级汇编号
int MinCost; //最小花费
char** InMap; //输入的地图
coordinate* m; //记录所有man的坐标
coordinate* H; //记录所有House的坐标
int* pre; //最小费用流路径上,结点i的前驱结点为pre[i]
int** cost; //两点间费用,其中超级源为0,1~n为man,n+1~2n为house,2n+1为超级汇
int** cap; //两点间容量,其中超级源为0,1~n为man,n+1~2n为house,2n+1为超级汇
int* dist; //超级源到各点的最短距离
bool* vist; //标记各点是否在队列
};
void solve::Input(void)
{
int i,j;
InMap=new char*[R];
for(i=0;i<R;i++)
{
InMap[i]=new char[C];
for(j=0;j<C;j++)
{
cin>>InMap[i][j];
if(InMap[i][j]=='m') //检查'm'
n++; //得到man or house的数量
}
}
return;
}
void solve::StructureBinaryMap(void)
{
int i,j;
int pm=0,pH=0;
m=new coordinate[n+1];
H=new coordinate[n+1];
/*记录各个man与house的坐标*/
for(i=0;i<R;i++)
for(j=0;j<C;j++)
if(InMap[i][j]=='m')
{
m[++pm].x=i;
m[pm].y=j;
}
else if(InMap[i][j]=='H')
{
H[++pH].x=i;
H[pH].y=j;
}
/*建立存储空间*/
cost=new int*[2*n+2];
cap=new int*[2*n+2];
for(i=0;i<2*n+2;i++)
{
cost[i]=new int[2*n+2];
cap[i]=new int[2*n+2];
memset(cost[i],0,sizeof(int)*(2*n+2)); //所有路径费用默认为0
memset(cap[i],0,sizeof(int)*(2*n+2)); //所有路径容量默认为0(饱和,不连通)
}
/*初始化超级源s到各个man的容量*/
s=0;
for(i=1;i<=n;i++)
cap[s][i]=1; //容量默认为1
/*初始化各个man到house的距离(费用)及容量*/
for(i=1;i<=n;i++)
for(j=n+1;j<=2*n;j++)
{
cost[i][j]=abs(m[i].x-H[j-n].x)+abs(m[i].y-H[j-n].y); //man到house的费用为abs(△x)+abs(△y)
cost[j][i]=-cost[i][j]; //注意顺便构造负权边
cap[i][j]=1;
}
/*初始化各个house到超级汇t的容量*/
t=2*n+1;
for(j=n+1;j<t;j++)
cap[j][t]=1; //容量默认为1
return;
}
bool solve::spfa(void)
{
dist[s]=0;
for(int i=1;i<2*n+2;i++) //注意这里不能用memset(),memset是对字节为单位进行赋值
dist[i]=inf(); //若非置0,memset对char、bool以外的类型都会赋一个与期望完全不同的数值
memset(vist,false,sizeof(bool)*(2*n+2));
vist[s]=true;
queue<int>q;
q.push(s);
while(!q.empty())
{
int u=q.front(); //获取队头元素
for(int v=0;v<=t;v++)
{
if(cap[u][v] && dist[v]>dist[u]+cost[u][v]) //u->v容量未饱和,且能够松弛
{
dist[v]=dist[u]+cost[u][v];
pre[v]=u; //记录u的前驱结点
if(!vist[v])
{
q.push(v);
vist[v]=true;
}
}
}
q.pop(); //队头元素出队
vist[u]=false;
}
if(dist[t]==inf()) //dist[t]没有被调整,说明已不存在增广链
return false;
return true; //找到一条当前费用和最小的增广链
}
void solve::AddMaxFlow(void)
{
int MaxFlow=inf(); //可分配最大流
int i;
for(i=t;i!=s;i=pre[i]) //可分配最大流 为增广链上的最小容量边的容量
MaxFlow=min(MaxFlow,cap[pre[i]][i]);
for(i=t;i!=s;i=pre[i]) //增广链上流量调整(增流)
{
cap[pre[i]][i]-=MaxFlow; //正向弧容量减去可分配最大流
cap[i][pre[i]]+=MaxFlow; //反向弧容量加上可分配最大流
MinCost+=cost[pre[i]][i]*MaxFlow; //最小费用=单位费用*流量
}
return;
}
int main(void)
{
int row,col;
while(cin>>row>>col && (row+col))
solve poj2195(row,col);
return 0;
}