HOJ 1021 Housing Complexes 解题报告

HOJ 1021 Housing Complexes 解题报告

By icycandy

题目大意：

住房部正在规划一个庞大的建设项目，他们看中了k块土地。这k块土地大小均为m*n，每块土最多只能盖一幢别墅，每幢别墅大小均为h*w，土地和别墅均为长方形。

由于这些土地上还住着一些钉子户（编号A-Z），因而政府需要付钱购买钉子户的房子。购买时遵循如下规则：如果要付钱购买房子，则在同一块土地上只购买同一个钉子户的，比如A；如果在某一块地上购买了A拥有的房子，则在其他土地上不再购买A的房子。

给出每块土地上钉子户的分布情况，求最多能盖多少幢房子。

k<=30;m,n<=50;h,w<=50。

算法分析：

最开始我理解错了题意，以为每块地只要大小允许，可以盖不止一幢别墅。实际情况中土贵如金，谁会如此奢侈？但是政府有钱，我们平头百姓有什么办法。

二分图匹配，以土地为X集合，钉子户为Y集合，二分图用map[ ][ ]表示，结果用result表示。对第i块土地，可以分如下两种情况考虑：

1． 该土地中不存在钉子户。

2． 该土地中存在钉子户，但不用购买任何钉子户的土地就可以有足购的空间盖起一幢别墅。

3．该土地空间不足以盖起一幢别墅，但当买下该块地中钉子户j的所有土地后，就有足购的空间。

初始时置result=0，map[i][j]=false。对于情况1和2，直接将result++即可；对于情况3，则置map[i][j]=true。对map[ ][ ]求最大二分匹配m，最后结果为result+m。

在情况3中判断买下j的土地是否空间足够，由于图最大也就50*50，直接枚举即可，四重循环。值得注意的是，土地和别墅的方向只有一种。如下图，也就是说在土地上，别墅只能横着盖，不能竖着盖。左边是正确的，右边是错误的。最开始我两种情况都考虑了，WA了好几次。其实正常来说，如果竖着盖能行，也应该是可以的呀。咱政府就是有钱，没办法。

求二分匹配我用的是匈牙利算法，DFS实现。匈牙利算法也可以用BFS或Hopcroft Carp实现，另外，求二分匹配也可以用网络流有关算法。DFS的优点是实现简洁、容易理解，而且对一般的题，效率也可以忍受。