题意:

一个地图上有很多小人要回家,每个小人都可以去任意一栋不同的房子,每个小人去一栋房子的花费为房子和人的曼哈顿距离。求最小支付多少花费可以使小人都回家?

思路:

直接套用最小费用最大流。1.把每个小人和每个房子连边,容量为1,费用为距离;2.把超级源点和每个小人连边,容量为1,费用为0;3.把每个房子和超级汇点连边,容量为1,费用为0.