当前位置:首页 > 图论 > 二分图 > 正文
HDU2255奔小康赚大钱
4123+

题目大意:n个人买n间房,已知他们对各个房间的出价,如何卖才能赚最多钱,最多能赚多少钱?

Problem Description

传说在遥远的地方有一个非常富裕的村落,有一天,村长决定进行制度改革:重新分配房子。

这可是一件大事,关系到人民的住房问题啊。村里共有n间房间,刚好有n家老百姓,考虑到每家都要有房住(如果有老百姓没房子住的话,容易引起不安定因素),每家必须分配到一间房子且只能得到一间房子。

另一方面,村长和另外的村领导希望得到最大的效益,这样村里的机构才会有钱.由于老百姓都比较富裕,他们都能对每一间房子在他们的经济范围内出一定的价格,比如有3间房子,一家老百姓可以对第一间出10万,对第2间出2万,对第3间出20万.(当然是在他们的经济范围内).现在这个问题就是村领导怎样分配房子才能使收入最大.(村民即使有钱购买一间房子但不一定能买到,要看村领导分配的).

Input

输入数据包含多组测试用例,每组数据的第一行输入n,表示房子的数量(也是老百姓家的数量),接下来有n行,每行n个数表示第i个村名对第j间房出的价格(n<=300)。

Output

请对每组数据输出最大的收入值,每组的输出占一行。

Sample Input

2
100 10
15 23

Sample Output

123

解题思路

n个人选n间房,各不相同,明显是二分图的完美匹配。现在要求效益最大,也就是权和最大的完美匹配,也就是找最佳匹配、最优匹配、最佳完美匹配、最优完美匹配……

用KM算法即可解决,可以这样做:一个一个人去匹配,匹配的时候,为了保证是最优最佳的,选择的边必定是边权最大那一条;如果对应的房子已经卖给其他人了怎么办?那么前一个人能不能在保持最优的情况下换个房子呢?如果可以,那换就是了,如果不行,看一下自己有没有其他也是最优的选择,如果实在没有其他最优的选择,那么这两个人必定有一个无法最优,让谁无法最优呢?看一下他们次大的边、次次大的边……选变化最小那个来换,这样就能保证失去的价值是最小的!

如何实现选择的是最优的边?用顶标来实现!每个点(包括人和房)都有一个顶标,记录他们的权值,一开始人的顶标dx是这个人的最高出价,房的顶标dy都是0,这样选边的时候,选两点权值之和等于边权的边,即dx+dy==mp[x][y],该选择肯定是最优的,因为这条边边权最大。如果发现y已经被买了,那就尝试让py换房;如果x和py都必须选择y这间房,那么总有一个选不了(找不到增广路),那就看谁的牺牲会小些,记录最小的利益牺牲值cha,然后搜索过的x点顶标全部减去cha,搜索过的y点顶标全部加上cha,这样并不影响原来的选择的效益,因为原来匹配好的,左边减去cha,右边必然加上cha,两点权值之和依然等于边权;原来没匹配的,绝对不会含有房子,因为有没匹配的房子就可以直接配对了;原来没匹配的人,只有1个,就是在找房子的那个人,因为其他人都是通过房子购买者找到的人。最终x顶标是多减了,但那是必须减的,因为同一个房子只能卖给一个人,此时减的是最小的了,顶标之和还是保持了最优。顶标减少后,就有可能找到其他“最优”的边,从而增加匹配数。

减了之后,后面有可能会加回来吗?a选了b后,aa要选b,因a换成bb损失最少,会导致a减小、b增大、aa减小,接着aa→b,a→bb;后来aaa要选b,因为aaa到b是边权最大的,aaa权值需要减少b权后再找b,aaa减少后,aa的权值要加回来吗?不需要!因为aa的权值虽然减少了,但也不比其他边权小(如果更小就不会这样匹配了),即使加回来了,后面还是会减回去的。

那么,如果发现两点顶标之和大于边权,能直接选择该边吗?答案是不可以的,因为可能有多条这样的边,我们需要先找到最大的边,这样顶标减少的值才是最小的。因此,还是需要先找到最小的效益差值,更新顶标后再寻找匹配

关于时间复杂度,dfs一次的时间复杂度是O(m+n)while(1)里面最多执行m次,因为每个点的顶标减少次数之和不超过边数(一个点有x条边,顶标最多为他更新x-1次),因此总的时间复杂度是O(m*m+m*n)

程序实现

About

坚决不Copy代码!

本文标签:,,,,,

HDU2255奔小康赚大钱:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!