KM算法总结

km算法我的理解

 

刷了不到20道题。。。回来总结一发。。

如果题目求的是最小权值匹配,比较好的做法是将权值取取值,最后res再取负就好。需要注意的是初始化的时候w和lx要比所有值都小,所以要ms(lx,0xc0)

最正确解最小权匹配的办法是用一个很大的数-当前边权值,而不是直接对边权取反(这样只能处理左右点相等的完全二分图,即K(n, n)(bin神博客看到的)

有时候需要考虑无解的情况,一般如果有无解的情况,对应了存在lx[i]=初始化的值。

不少题目有一个点都是先用一种暴力或者不暴力的方法处理出w,然后裸的km  hdu3722解题报告

有向图的覆盖可以对应二分图最佳匹配的模型,用km算法搞 hdu1853解题报告

遇到了一种题是之前有一些已经安排好了,然后仍然求最优匹配,并且尽可能少得改变原有的安排。hdu2853解题报告 不得不说做法很厉害。

 

还有一些网络流的题似乎也可以转化成km来做,打算先去搞一发网络流再去A.

选区_077

这些题里就两个比较好,一个是对于有向环覆盖的,第一次遇到真想不到,还有一个就是那个权值×k的。。。佩服。。。

其他的都是套路。

HDU 3523 Image copy detection (二分图最佳匹配,KM算法,题意杀)

hdu 3523 题目链接

 

题意:有m个排列,每个排列有n个,然后要找一个长度为n的排列(1..n每个数字恰好出现一次),使得这个排列到其他m个排列的距离之和最小。 两个排列之间的距离是对应位置上数字差的绝对值的和。

 

思路:妈蛋,什么鬼题面。。。看不懂。。。然后看了题解。。。知道了题意。。

的的确确做过相当类似的一道呢。

先n*n*n的复杂度(1E6)处理权值,然后KM.

1A.

 

 

 

 

hdu 2853 Assignment (二分图最佳匹配,KM算法+数论,做法太神)

hdu 2853题目链接

题意:n个公司,m个任务(m>=n),一个公司只能对应一个任务,一个任务也只能对应一个公司。给出一个n*m的mat,表示每个公司对应每个任务产生的val。  然后给出n个数,表示初始钦定(雾)这n个公司分别做哪些任务。 但是可能初始的安排得到的val表示最大的。我们现在想得到最大的val,并且保证改变的安排数最少。求安排后得到的 val比初始安排大多少,以及需要改变的安排数量。

思路:最大val很好求,KM就好。。。但是,怎么才能保证改变的安排数最少呢? 尤其是当两个安排val一样的时候,如何才能保证优先选已经安排好的,而不取选另一个呢?

并没有想出来,看了题解T T

太神辣。

由于KM算法会根据权值来选取,权值大的会优先。

如果我们把每个权值*k(k>n),然后对于已经钦定的安排,每个权值再+1.

这样,钦定的安排就会有更高的优先级,最后统计的时候除以k,那么权值答案不会有影响(利用到了初等数论的整除知识。。。?)

然后这样做该有一个好处。

不除以k的权值和再模k,就是没有改变的安排数。

原因是由于没有钦定的安排的权值每个都乘了k,最后%k都为0,只有那些钦定的安排每个会贡献1.

又由于k>n,这样就保证了正确性。

 

这做法太神了。。。。。吓傻了。。。。

我试着推广一下。。。?

对于根据权值来决定优先顺序,但是权值相同的时候还是需要对一些赋有更高的优先权的模型。。。?

除了再增加一维的大家都能想到的做法。。。这样的做法是不是有通用性呢。。。?

做法太神,我得慢慢体会。。

 

 

 

 

hdu 2448 Mining Station on the Sea (floyd+KM)

hdu2448 题目链接

题意:n个船n个港口,一个港口只能承接一个船,m个油田,给出n个船各自在哪个油田,然后给出m个油田之间的无相图,然后给出油田和港口之间的有向图。求n个船到达港口的最小距离之和。

思路:想到了用floyd先更新一下距离,然后KM.不过思维不够严谨,只更新了港口通过油田到达油田的距离,而没有更新油田通过油田到达油田的距离QAQ.

所以应该先更新油田通过油田到达油田的距离,然后再更新港口通过油田到达油田的距离。。。

哦,还有。。。不要把n个船所对应的港口作为下标。。而是转化成1..n,这样写KM里会比较好写。。。不然总得带着那个id[i].

 

选区_074

 

 

 

hdu 3718 Similarity (二分图最优匹配,KM算法)

hdu 3718题目链接

题意:东西分类作业,有n个东西,k组,m个学生,不同种类的东西用不同的字母表示,相同种类的用同一个字母表示。不同学生和标准答案之间可能表示同一类东西用的字母不同,但是字母只是一个标号(But the LABEL of group doesn’t make sense and the LABEL is just used to indicate different groups. ) 给出事物分类的标准答案和每个学生的答案现在问每个学生的正确率是多少。

思路:用map<char,int>把字母转化成点的标号。然后初始化权值为0. 对于每个学生,o(n)扫一遍统计出w。然后做一遍KM求最大正确数。从而得到正确率。 因为一个map忘记每次清空,WA了一次。。。2A..

 

 

 

hdu 3722 Card Game (有向环覆盖,拆点,二分图最佳匹配,KM算法)

hdu 3722题目链接

题意:n个串,a串放在b串前面的val值是“The score of sticking two cards is the longest common prefix of the second card and the reverse of the first card”.问如何放使得总的val最大。

思路:先暴力处理出每两个的权值。。200*200*1000的复杂度。。还是可以接受的。。

然后把每个串看成了一个点,由于一个串最多可以被放在前面一次,被放在后面一次,所以可以类比图论中的环的入度和出度为1.

然后跑一遍KM. 1A,开心。

 

hdu 3435 A new Graph Game (有向环覆盖,拆点,二分图最优匹配,KM算法)

hdu 3435题目链接

题意:给你一张图,图上可能有多个哈密顿回路。叫你求出形成多个哈密顿回路的总距离最小值

思路:题意杀啊。。。什么鬼了。。。然后时间。。1000的数据。。n3复杂度。。。还多组数据。。。。不是很懂这个时间是怎么算的。。为毛才2600MS啊。。。。

选区_073

 

做法同hdu 1853…

 

 

hdu 1853 Cyclic Tour (有向环覆盖,拆点,二分图最佳匹配,KM算法)

hdu 1853 题目链接

题意:一个带权有向图,要求找出若干的环,满足每个点恰好在一个环里,并且环的权值和最小……问最小权值和。

思路:没有思路,不知道怎么处理环的问题。于是去群里问了下。正确做法是拆点

如果有一条边i->j,那么就连一条i->j’的边。

正确性:

对于满足条件的环,每个点的入度和出度均为1,我们可以把每个点拆成入点和出点,那么也就是说一个入点对应一个出点,反之亦然,那么这个问题就变成了一个二分图匹配问题,

 

然后这道题有重边,2A.

又一次体会到了拆点的神奇。。。这个大概算是需要慢慢积累的技巧吧。。像辅助线一样的。。。

还有体会到了环的模型竟然也可以转化成二分图匹配,真是厉害==

 

hdu 2813 One fihgt one (二分图最优匹配,KM算法)

hdu 2813 题目链接

题意:吕布有n个武将,曹操有m(m>=n)个武将。给出k个关系,为吕布的某个武将和曹操的某个武将pk后会受到的伤害。吕布要求他所有n的武将都要上场,每个武将只能战斗一次,问如何安排,使得所有武将受到的伤害总和最小。

思路:裸的KM。 用map把武将名字变成点的编号。

 

hdu 2282 Chocolate (二分图最优匹配,KM算法)

hdu 2282 题目链接

题意:n个盒子围成一个圈,给出n个盒子中每个盒子中的巧克力个数,巧克力的总数不超过n,从一个盒子中移动一块巧克力到相邻的盒子里称为one “move”,(由于围成一个圈,所以第1个和第n个盒子也是相邻的) 问最小的移动“move”数,使得每个盒子里最多有一快巧克力。

思路:先记录每块巧克力的位置,为了之后算w,然后将巧克力和盒子分别看做X,Y集合。。。建图。 然后KM   。。1A

 

hdu 3395 Special Fish (二分图最佳匹配,KM算法)

hdu 3395题目链接

题意:鱼,一些鱼认为自己是汉子,然后他会去和他认为是妹子的鱼啪啪啪,然后被啪啪啪的妹子就会产卵? 卵的val是它parent的val的异或。给出n,为鱼的数量,然后给出一个n*n的 mat,a[i][j]==1表示第i条鱼认为第j条鱼是妹子。问卵的最大val之和是多少。需要注意的是:每条鱼最多可以去和一个妹子啪,并且可以作为妹子被啪一次(这两个是独立的。。。) (Each fish can attack one other fish and can only be attacked once)

 

思路:二分图最佳匹配,KM算法,2A.

 

hdu 2426 Interesting Housing Problem (二分图最佳匹配,km算法)

hdu 2426 题目链接

题意:n个学生,m个宿舍,每个学生住一个宿舍,然后n个学生给若干个宿舍打分,分数可正可0可负,学生不能住打的分为负的宿舍,或者没有打分的宿舍。问在满足上述条件的前提下,所有学生住的宿舍的分数之和最大是多少。如果无解输出-1.

 

思路:二分图最佳匹配。。。读漏题QAQ. 原来分数为负的房间是不能住的啊。。。。

考虑无解的情况,如果学生数比宿舍数多,无解。

如果一个学生不喜欢任何宿舍或者没给任何宿舍打分,无解。

然后KM.

 

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里多的一个步骤,并且是容易忘记的。。。

 

 

 

 

hdu 2255 奔小康赚大钱 (二分图最佳匹配,KM算法模板题)

hdu 2255 题目链接

 

题意:传说在遥远的地方有一个非常富裕的村落,有一天,村长决定进行制度改革:重新分配房子。
这可是一件大事,关系到人民的住房问题啊。村里共有n间房间,刚好有n家老百姓,考虑到每家都要有房住(如果有老百姓没房子住的话,容易引起不安定因素),每家必须分配到一间房子且只能得到一间房子。
另一方面,村长和另外的村领导希望得到最大的效益,这样村里的机构才会有钱.由于老百姓都比较富裕,他们都能对每一间房子在他们的经济范围内出一定的价格,比如有3间房子,一家老百姓可以对第一间出10万,对第2间出2万,对第3间出20万.(当然是在他们的经济范围内).现在这个问题就是村领导怎样分配房子才能使收入最大.(村民即使有钱购买一间房子但不一定能买到,要看村领导分配的).

 

思路:这是一道裸的二分图最佳匹配题目。

如果G为加权二分图,则权值和最大的完备匹配称为最佳匹配.

解决二分图最佳匹配的常用算法为KM算法,该算法的前置技能点为匈牙利算法。

参考了以下文章:
关于KM算法的详细解释
km算法
求最大权二分匹配的KM算法

km算法模板

 

先粗浅得说下我对这个算法的理解,等A掉足够多的题目之后再回来总结。

因为才刚刚学习这个算法,可能有很多没理解透彻或者理解错误的地方,还望各位多多指教。

 

KM算法引入了一个交顶标的概念,lx[i]表示X集合中第i个点的顶标,ly[i]表示Y集合中第i个点的顶标。至于这个顶标具体代表什么先不用考虑,只需要知道,这个概念的引入是为了解决二分图最佳匹配的问题。

如果一组xi,yi,满足lx[xi]+ly[yi]-w[xi][yi]>=0成立,那么我们称这组点为【可行的】

我们要时刻保证每组点都是可行的。

如果我们把所有满足lx[xi]+ly[yi]==w[xi][yi]的(xi,yi)导出,形成一个新的图,那么新图的最大匹配一定是原图的最佳匹配。原因也很简单:新图的权值和等于所有的顶标和,而根据【可行】点对的定义,最好的情况就是所有不等式都取了等号。

为了保证初始时lx[xi]+ly[yi]-w[xi][yi]对于任意xi,yi成立,不妨这样构造lx[],ly[]:

lx[i]=max(w[i][j]),(1=<j<=ny) ,ly[i]=0;

注意是“不妨”,也就是初始值并不是唯一的,只不过这种构造方法在满足不等式的前提下相对简单。

然后就和hungary算法基本类似,从每一个X集合中的点开始寻找增广路。

但是。。但是哪有那么好的事情。。。就那么恰好满足lx[xi]+ly[yi]=w[xi][yi]了。。?

没有满足的怎么办。

 

接下来就要说KM算法最关键的一步,调整顶标

我们调整顶标的目的是让更多的点对满足式子lx[xi]+ly[yi]==w[xi][yi],从而进入相等子图,直到图中存在仅由可行边组成的完全匹配为止.

调整的过程中仍然要保证所有点对都【可行】也就是保证lx[xi]+ly[yi]>=w[xi][yi]一直成立。

由于当前lx[xi]+ly[yi]-w[xi][yi]是比我们预期的大,所以我们要想办法减小。

具体方法为:

方法为:将所有在增广轨中(就是在增广过程中遍历到)的X方点的标号全部减去一个常数d,所有在增广轨中的Y方点的标号全部加上一个常数d,则对于图中的任意一条边(i, j, W)(i为X方点,j为Y方点):

 

点对经过调整后分为四种情况:

<1>i和j都在增广轨中:此时边(i, j)的(lx[i]+ly[j])值不变,也就是这条边的可行性不变(原来是可行边则现在仍是,原来不是则现在仍不是);
<2>i在增广轨中而j不在:此时边(i, j)的(lx[i]+ly[j])的值减少了d,也就是原来这条边不是可行边(否则j就会被遍历到了),而现在可能是;
<3>j在增广轨中而i不在:此时边(i, j)的(lx[i]+ly[j])的值增加了d,也就是原来这条边不是可行边(若这条边是可行边,则在遍历到j时会紧接着执行DFS(i),此时i就会被遍历到),现在仍不是;

<4>i和j都不在增广轨中:此时边(i, j)的(lx[i]+ly[j])值不变,也就是这条边的可行性不变。

简单得说:(1) (3)(4)三种情况,不会改变一组点的可行性,用白话解释就是,以前满足那个等式而进入相等子图的点对不会因为调整而从相等子图中出来,以前不满足那个等式的点不会因为调整而进入相等子图。

而对于情况(2),因为lx[xi]+ly[yi]-w[xi][yi]减少了,那么以前不满足,现在有可能满足。注意,现在还只是可能满足。

那么这个常数d到底是多少?怎么确定?

是的,接下来的着手点就在这个d上。

那么d的值应取多少?显然,整个点标不能失去可行性,也就是对于上述的第<2>类边,其lx[i]+ly[j]>=W这一性质不能被改变,故取所有第<2>类边的(lx[i]+ly[j]-W)的最小值作为d值即可。这样一方面可以保证点标的可行性,另一方面,经过这一步后,图中至少会增加一条可行边。

这样的最小值d,会恰好使得得到最小值d的那组点对的lx[i]+ly[j]-w的值从大于0变成0(好像是废话,我只是为了强调一下)

但是如果朴素得去找最小值更新d的话,复杂度是O(n4)(不会分析复杂度。。。mzdd)