KM算法(二分图的最佳完美匹配)

  网上一堆人写KM算法,还没搜出哪个讲得比较好的。

  KM算法大概过程:

  (1)初始化Lx数组为该boy的一条权值最大的出边。初始化Ly数组为 0。

  (2)对于每个boy,用DFS为其找到一个girl对象,顺路记录下S和T集,并更新每个girl的slack值。若不能为其找到对象,则转3。

  (3)找出非T集合的girl的最小slack值为d,更新S集中的boy和T集中的girl,并且顺路更新非T集中的slack值。对于那个失败的boy继续第2步。

  简括之,就是在保持当前权和最高的情况下,尽量为每个boy找到权更大的边。找的过程就是DFS过程,标记出S和T集是为了保证权和最大,因为只要帮S中任意一个boy另找一个女对象,为这个boy的此次脱单之路告终。

  DFS的要完成的任务:

  (1)标记S和T集。

  (2)更新每个girl的slack值为最小。

  模板还是必须的,带满了注释,改自kuangbin的模板。

  

 1 /* KM算法
 2 * 复杂度O(nx*nx*ny)
 3 * 求最大权匹配(貌似只能求完美匹配?)
 4 * 若求最小权匹配,可将权值取相反数,结果取相反数
 5 * 点的编号从1开始
 6 * 模板以男女模型比较直观。
 7 */
 8 int  nx, ny;                  //两边的点数,x为男,y为女。
 9 int  g[N][N];                 //二分图描述,g[x][y]。
10 int  girl[N], Lx[N], Ly[N];   //girl[i]记录i的匹配成功对象,男女的顶标
11 int  slack[N];      //为了优化用的,连接到对应girl的一条松弛值。
12 bool S[N], T[N];    //匈牙利树的节点集合,S为男,T为女。
13
14 bool DFS(int x) // x一定是个男的
15 {
16     S[x]=true;
17     for(int i=1; i<=ny; i++) //对于每个女的
18     {
19         if(T[i]) continue;
20         int tmp=Lx[x]+Ly[i]-g[x][i];
21         if( tmp==0 )
22         {
23             T[i]=true;
24             if(girl[i]==-1 || DFS(girl[i])) //为第i个girl的男对象另找女对象
25             {
26                 girl[i]=x;      //记录匹配的boy
27                 return true;
28             }
29         }
30         else if(slack[i]>tmp)   //顺便更新下slack
31             slack[i]=tmp;
32     }
33     return false;
34 }
35
36 int KM()
37 {
38     memset(girl, -1, sizeof(girl));
39     memset(Ly, 0, sizeof(Ly));
40
41     for(int i=1; i<=nx; i++) //初始化两个L数组分别为-INF和0
42     {
43         lx[i] = -INF;
44         for(int j=1; j<=ny; j++)
45             if(g[i][j]>lx[i])
46                 lx[i]=g[i][j];
47     }
48
49     for(int j=1; j<=nx; j++)     //对于每个男人
50     {
51         for(int i=1; i<=ny; i++)           //初始时slack为无穷。slack只需要记录女人的。
52             slack[i]=INF;
53
54         while(true)     //无限循环,直到帮其找到对象
55         {
56             memset(S, 0, sizeof(S));
57             memset(T, 0, sizeof(T));
58
59             if( DFS(j) )  break;    //直接就找到对象了,搞定。
60
61             int d=INF;
62             for(int i=1; i<=ny; i++)       //根据不在匈牙利树上的女人的slack找到最小值d
63                 if(!T[i] && d>slack[i])
64                     d=slack[i];
65
66             for(int i=1; i<=nx; i++)     //所有匈牙利树上的男人更新lx值
67                 if(S[i])
68                     Lx[i]-=d;
69
70             for(int i=1; i<=ny; i++)     //树上的女人加d,不在树上的女人的slack减d。
71             {
72                 if(T[i])     Ly[i]+=d;      //这是为了让等式仍然成立
73                 else         slack[i]-=d;   //为何要做这一步?
74             }
75         }
76     }
77     int ans=0;
78     for(int i=1; i<=ny; i++)       //累计匹配边的权和
79         if(girl[i]>0)
80             ans+=g[girl[i]][i];
81     return ans;
82 }

KM算法模板

时间: 08-08

KM算法(二分图的最佳完美匹配)的相关文章

HDU_2255 二分图最佳完美匹配 KM匈牙利算法

一开始还没看懂这个算法,后来看了陶叔去年的PPT的实例演示才弄懂 用一个lx[]和ly[]来记录X和Y集合中点的权值,有个定理是 lx[i]+ly[j]==w[i][j](边权值) 则该点是最佳匹配,因为首先 那个不等式肯定要>=的,否则就不满足题意了,如果是>则可以去匹配更有价值的边或者把权值降下来让匹配边的潜力更大. 所以只有把握了这个条件,其他就是走一遍最大匹配数.以及up()函数用来在无法匹配的时候,进行其他点的权值降低(也可以说是增广路的搜索)来得到匹配. #include <

UVALive 4043 转化最佳完美匹配

首先黑点和白点是组成一个二分图这毫无疑问 关键是题目中要求的所有黑白配的线不能交叉...一开始我也没想到这个怎么转化为二分图里面的算法. 后来看书才知道,如果两两交叉,则可以把两根线当四边形的对角线,连四边形的两条边,则肯定不交叉,而且一个很明显的特征是,不交叉的两条线的他们的长度和 一定比交叉线的长度和小. 于是我们只要求出最小长度的线,就必定是不相交的.那就要用到最佳完美匹配了,首先算出两两点的欧几里得距离,然后取负数,这样走一遍匹配,得到的必定是最短的欧几里得距离,即不相交的线 #incl

UVALive 4043 Ants 蚂蚁(二分图最佳完美匹配)

题意:n个蚂蚁n棵树,蚂蚁与树要配对,在配对成功的一对之间连一条线段,要求所有线段不能相交.按顺序输出蚂蚁所匹配的树. 思路:这个题目真是技巧啊,如果知道要求的就是整体最优,那么就容易做了.而不能用贪心来为每个蚂蚁选择最近的树,这样可能八成还是相交了. 整体最优能让每条线段不相交,证明: 假设a1-b1与a2-b2相交.则dis(a1,b1)+dis(a2,b2)>=dis(a1,b2)+dis(a2,b1).如果我们所决定的最优匹配是按照整体距离最短来匹配的,那么dis(a1,b1)+dis(

1076. Trash(KM算法 二分最佳完美匹配)

1076. Trash Time limit: 1.0 second Memory limit: 64 MB You were just hired as CEO of the local junkyard.One of your jobs is dealing with the incoming trash and sorting it for recycling.The trash comes every day in N containers and each of these conta

KM算法详解[转]

KM算法详解 原帖链接:http://www.cnblogs.com/zpfbuaa/p/7218607.html#_label0 阅读目录 二分图博客推荐 匈牙利算法步骤 匈牙利算法博客推荐 KM算法步骤 KM算法标杆(又名顶标)的引入 KM流程详解 KM算法博客推荐 0.二分图 二分图的概念 二分图又称作二部图,是图论中的一种特殊模型. 设G=(V, E)是一个无向图.如果顶点集V可分割为两个互不相交的子集X和Y,并且图中每条边连接的两个顶点一个在X中,另一个在Y中,则称图G为二分图. 可以

KM算法(最优匹配)

最优匹配看了好多天,哎,就是因为一个细节问题没注意到,不知道网上的讲的不清还是本人智商不够,现在把我的误区说一下吧,顺便讲一下KM 算法,希望看KM算法的知识青年能少走弯路 KM算法是解决最优匹配问题的,关于最优匹配的相关术语网上说的很详细,可以先参考这个网站看下,http://philoscience.iteye.com/blog/1754498,本博客建立在此网站的基础上做的补充,是因为限于时间吧不能写的很详尽,希望对大家能有所帮助. 直入主题吧 最优匹配:举个栗子,比如为每边输入n(n=5

【km算法模板+总结】

今天下午看了一下午的km算法,因为大佬的博客介绍非常简短,所以自己一直没有弄清楚一些细节问题,好在回来翻到了一个比较好的csdn专栏,介绍比较详细,自己才算弄懂了很多疑惑的地方,二分图最佳完美匹配. 总结一下算法: 思想:km算法就是改变一些可行点的标号,不断增加图中可行边的总数,直到图中存在仅由可行边组成的完美匹配为止.核心部分就是控制修改可行顶标的值直到最终可到达一个完美匹配. 流程:1)初始化可行顶标lx和ly的值(ly=0显然是可行的,保证任意x一个x方点至少一条可行边) 2)从每个x方

hdu2255 奔小康赚大钱 二分图最佳匹配--KM算法

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

(转)二分图的最大匹配、完美匹配和匈牙利算法

转载自http://www.renfei.org/blog/bipartite-matching.html 二分图的最大匹配.完美匹配和匈牙利算法 这篇文章讲无权二分图(unweighted bipartite graph)的最大匹配(maximum matching)和完美匹配(perfect matching),以及用于求解匹配的匈牙利算法(Hungarian Algorithm):不讲带权二分图的最佳匹配. 二分图:简单来说,如果图中点可以被分为两组,并且使得所有边都跨越组的边界,则这就是