KM

POJ-2195 Going Home

题目传送门: POJ 2195

给一张图,图上标记号小人与房子,小人的数目等于房子的数目,要求每个小人都走入不同的房子,小人能够水平或者竖直移动,每移动一格花费一,可以走过房子而不进入,问最小的花费。

KM模板题,用最大权匹配做,把边权变为负值就变成了最小权匹配。