hdu 1533 Going Home (二分图最佳匹配,KM算法)

hdu 1533 题目链接

题意:给出一个n*m的maze,其中包含不超过一个人(用m表示),以及和人数相等的房子(用H表示),其他都是‘.’,表示可以经过的路径。人向一个方向移动花费代价1.问每个人都回到一个房子里的最小代价是多少。ps:每个格子是无限大的,也就是所有人可以同时踩在一个格子里。以及:路过一个房子可以不住,而只是“经过”。

思路:有了那两个条件,这题就是赤裸的二分图最优匹配了。建图也很easy.可以预处理下w,就是两点的哈密顿距离.

需要注意的是这道题求的是最小权值。那么做法就是将w取负,然后答案再次取负即可

(还有其他方法处理,不过这种最easy应该?)

(不过要保证初始化某些数组的时候要比所有的值小,所以不能是0,而应该是-inf)

以及:初始化数组为-inf的方法,可以memset(lx,0xc0,sizeof(lx));

这样得到的-inf只和inf的绝对值差1,好评如潮。

0xc0,0xc0,0xc0,重要的常数说三遍

 

哦还有,不要忘记在每次find的时候记录X集合中的点,这是比hungary算法的find里多的一个步骤,并且是容易忘记的。。。

 

 

 

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz