1
18
2015
0

KM算法

有个北大的教授来学校讲了《社会问题的中的计算机思维浅赏》。

讲到有关二部图问题的地方发现很像KM算法,就把KM拿出来复(yu)习(xi)了一遍。 

 

简介:

    用来解决带权二部图匹配。

优势:

    相比费用流,常数小,代码复杂度低。

    适用于某些特定的题目。

简介:

     定义一个二部图G,左顶点为X,右顶点为Y,边权为Wij。

     设左顶点上有点标A,右顶点B,满足对于任意的点对(i,j),Ai+Bj>=Wij。

     引理定义二部图G的一个以 (X , Y , 所有满足Ai+Bj==Wij的边) 组成的集合为S。

           那么,对于一个S的完备匹配,一定是G的最大完备匹配。

           此时,这个完备匹配对应的答案即为所有的顶标和。

     伪证明如果G的某一个完备匹配的某条边(i,j)不在集合S中,那么Wij<=Ai+Bj,所以不然不会比S中的完备匹配优。

     算法流程:

         1.初始化顶标。对于X,每个点的顶标为这个点连出去的边的边权的最大值。对于Y,顶标为0。

         2.寻找交错路。直到无法找到。

         3.设dij=Ai+Bi-Wij,对于X中在交错路中的点,找到Y中不在交错路中的点,为(i,j),找到所有满足条件的点对中dij最小的点对。

           把交错路中的所有X顶标-dij,交错路中的Y顶标+dij。

           { 此时,对于一条边(i,j)。

             若i在交错路中,j也在交错路中,那么Ai-dij+Bi+dij==Ai+Bi==Wij。 (无影响)

             若i不在交错路中,j也不在交错路中,那么Ai+Bi>Wij。 (无影响)

             若i在交错路中,j不在交错路中Ai+Bj>Ai-dij+Bj>=Wij。 (有可能进入S集合)

             若i不在交错路,j在交错路中Ai+Bj+dij>Ai+Bj>Wij。 (不可能进入S集合)

           }

           通过上述操作,我们把至少一条边加入了S集合。

         4.重复(2)(3)直到找到完备匹配。

         注意:在步骤3中,我们可以在匈牙利找交错路的时候顺带在Y中记下和这个点相连的在交错路中的X的最近距离,slack数组来快速找到dij。

         复杂度:这里我很纳闷,我觉得每次改点标必然加入一条边,最多改O(m)次点标,每次改点标要做一次匈牙利增广O(n+m),我认为复杂度是O(m*(n+m))的,但是网上都                  说是O(n^3),希望有人能帮我指正!!! 确实是O(n*m),不过现在太迟了,不想写了。。。明天还要跑1km 

应用:

    二分图带权匹配就不说了,费用流直接上就可以了。

    SHOI2004MST,题意是给定一张图G和G的一棵生成树T,让你修改最小的边权使T是G的最小生成树。

    对于T上的边,他一定是增加的,不在T上的边一定是减小的。

    设边权为p,修改大小为d。

    对于一条不在T上的边i,设他在T上跨越的边j,需要满足 pi+di>=pj-dj -> di+dj>=-pi+pj。

    观察式子发现它很像KM的Ai+Bj>=Wij,然后转化为KM的点标和,直接上KM。

    至于为什么KM跑出来的点标是最小的,我只能给出伪证明:

    对于一个S的完备匹配,修改任何一个点的点权,使其减小d,其在另一部中对应的点权必然增加d,否则Ai+Bj>=Wij就不成立了。因此解无法变得更小。所以是最优解。

    类似条件为Ai+Bj>=Wij且要求Ai,Bj的和最小的题目都可以用KM来解。

后记:

    教授会动态修改Wij的KM算法哦。虽然复杂度是O(m^2*n*),而且算不上KM。

若有口糊请当作没听到。。求不D。。求不黑。。若有错误,欢迎指(jiao)正(yu)。。

Category: 未分类 | Tags: KM算法 网络流 | Read Count: 806

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com