题意： 给一张n * m（100 * 100）的图，图中” . " 代表空地， “ M ” 代表人， “ H ” 代表家。 现在，要你安排每个人从他所在的地方移动到家里，每移动一格的消耗是1，求最小的消耗。 人可以移动到家的那一格但是不进去。 解析： 先用bfs搞出每个M与每个H的距离。 然后就是网络流的建图过程了，先抽象出源点s和汇点t。 令源点与每个人相连，容量为1，费用为

之前这道题用了费用流来解决，这次用了二分图最佳匹配来解决。        不过，用二分图最佳匹配解决这道题时，要注意题目要求花费最小，所以是求权值之和最小的最佳匹配。要用一个大数减去原有权值作为新的权值，最后输出答案时，要注意还原真正的权值。        通过这道题，也可以发现费用流与二分图最佳匹配之间有所关联，而且就这道题来看，二分图的代码量会小于费用流的代码量，所以尽可能采

题目链接：http://poj.org/problem?id=2195 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, t

还是KM算法，求最小值的匹配，建图的时候，边都取反就可以转化成求最大值的匹配了。#include<string.h>#include<iostream># define inf 1000000using namespace std;int m,n,x,y,ans;int map[101][101],visx[101],visy[101],ly[101],lx[101],link[101

题意：有n个人，n个房子，一个人每走一步（可上、下、左、右取一个方向）花费1美元，问让这n个人走到n个房子里最少需要多少美元(n <= 100)。 题目链接：http://poj.org/problem?id=2195 ——>>在学最小费用最大流，找模版题找到了这道。 建图：1到n为人的编号，n+1到2*n为房子的编号，另加上源点0和汇点2*n+1； 源点到每个人各建立一条容量为1的流，费