算法学习：图论之二分图的最优匹配(KM算法)

图论中的二分图匹配问题及其算法设计思路图论是数学中一个重要的分支，研究图的性质和结构，以及解决与图相关的问题。

其中，二分图匹配问题是图论中的经典问题之一。

本文将介绍二分图匹配问题的定义、特性，并讨论相关的算法设计思路。

一、二分图匹配问题的定义二分图是一种特殊的图结构，其中的顶点可以分为两个互不相交的集合，且每条边都只连接两个集合之间的顶点。

对于一个二分图，如果存在一种边的划分方式，使得每个顶点都与边集中的一条边相连，那么我们称这个边集为二分图的一个匹配。

二分图匹配问题的目标是寻找出一个匹配，使得匹配的边数最大。

这个问题在实际应用中有许多场景，比如婚姻匹配、求职配对等。

为了解决这个问题，人们提出了多种算法，下面将介绍其中两个常用的算法。

二、匈牙利算法匈牙利算法是用于求解二分图最大匹配的一种经典算法，它基于深度优先搜索的思想。

算法的基本思路是从一个没有匹配边的顶点开始，逐个尝试与其相连的顶点进行匹配，如果能成功匹配则将边加入匹配集合中，如果不能成功匹配则继续尝试下一个顶点。

当所有的顶点都尝试过后，即得到一个最大匹配。

以下是匈牙利算法的伪代码：1. 初始化匹配集合为空2. 从一个未匹配的顶点开始，对其进行深度优先搜索3. 如果找到了增广路径，则更新匹配集合4. 重复步骤2和3，直到无法找到增广路径5. 返回最大匹配匈牙利算法的时间复杂度为O(V*E)，其中V表示顶点数，E表示边数。

虽然算法的时间复杂度较高，但它在实际应用中仍然具有一定的效率和适用性。

三、Hopcroft-Karp算法Hopcroft-Karp算法是用于求解二分图最大匹配的另一种算法，它是对匈牙利算法的改进和优化。

Hopcroft-Karp算法的核心思想是通过多次的广度优先搜索来寻找增广路径，从而提高算法的效率。

以下是Hopcroft-Karp算法的伪代码：1. 初始化匹配集合为空2. 初始化标记集合为空3. 利用广度优先搜索寻找增广路径4. 如果找到增广路径，则更新匹配集合5. 重复步骤3和4，直到无法找到增广路径6. 返回最大匹配Hopcroft-Karp算法的时间复杂度为O(E*sqrt(V))，相比于匈牙利算法有较大的优势。

Maigo的KM算法讲解(的确精彩)顶点Ｙｉ的顶标为B［i]，顶点Xi与Yj之间的边权为w[ｉ,j]。

在算法执行过程中的任一时刻，对于任一条边(ｉ,j),A［i]+B[j]>=w［i,ｊ]始终成立。

KM 算法的正确性基于以下定理：* 若由二分图中所有满足A［i］+B[j]=ｗ[ｉ,ｊ］的边（i，ｊ)构成的子图（称做相等子图）有完备匹配,那么这个完备匹配就是二分图的最大权匹配。

这个定理是显然的。

因为对于二分图的任意一个匹配，如果它包含于相等子图,那么它的边权和等于所有顶点的顶标和；如果它有的边不包含于相等子图,那么它的边权和小于所有顶点的顶标和。

所以相等子图的完备匹配一定是二分图的最大权匹配。

初始时为了使A［ｉ]＋B[j]>=w[i,j]恒成立,令A[i]为所有与顶点Xi关联的边的最大权，Ｂ[ｊ］＝0。

如果当前的相等子图没有完备匹配,就按下面的方法修改顶标以使扩大相等子图，直到相等子图具有完备匹配为止。

我们求当前相等子图的完备匹配失败了,是因为对于某个Ｘ顶点,我们找不到一条从它出发的交错路。

这时我们获得了一棵交错树,它的叶子结点全部是X顶点。

现在我们把交错树中X顶点的顶标全都减小某个值ｄ,Y顶点的顶标全都增加同一个值d，那么我们会发现：两端都在交错树中的边(i，j）,A［i]+B[j]的值没有变化。

也就是说,它原来属于相等子图，现在仍属于相等子图。

两端都不在交错树中的边(ｉ，ｊ)，A[i］和B[j]都没有变化。

也就是说,它原来属于(或不属于)相等子图，现在仍属于(或不属于)相等子图。

X端不在交错树中，Y端在交错树中的边(i，ｊ)，它的Ａ［ｉ]+B[j]的值有所增大。

它原来不属于相等子图,现在仍不属于相等子图。

X端在交错树中,Ｙ端不在交错树中的边（i,j),它的A［ｉ]+B[j]的值有所减小。

也就说,它原来不属于相等子图，现在可能进入了相等子图,因而使相等子图得到了扩大。

现在的问题就是求d值了。

前言：高中时候老师讲这个就听得迷迷糊糊，有一晚花了通宵看KM的Pascal代码，大概知道过程了，后来老师说不是重点，所以忘的差不多了。

都知道二分图匹配是个难点，我这周花了些时间研究了一下这两个算法，总结一下1.基本概念M代表匹配集合未盖点：不与任何一条属于M的边相连的点交错轨：属于M的边与不属于M的边交替出现的轨（链）可增广轨：两端点是未盖点的交错轨判断M是最大匹配的标准：M中不存在可增广轨2.最大匹配，匈牙利算法时间复杂度：O(|V||E|)原理：寻找M的可增广轨P，P包含2k+1条边，其中k条属于M，k+1条不属于M。

修改M 为M&P。

即这条轨进行与M进行对称差分运算。

所谓对称差分运算，就是比如X和Y都是集合，X&Y=(X并Y)-(x交Y)有一个定理是：M&P的边数是|M|+1，因此对称差分运算扩大了M实现：关于这个实现，有DFS和BFS两种方法。

先列出DFS的代码，带注释。

这段代码来自中山大学的教材核心部分在dfs(x)，来寻找可增广轨。

如果找到的话，在Hungarian()中，最大匹配数加一。

这是用了刚才提到的定理。

大家可以想想初始状态是什么，又是如何变化的view plaincopy to clipboardprint?第二种方法BFS，来自我的学长cnhawk核心步骤还是寻找可增广链，过程是：1.从左的一个未匹配点开始，把所有她相连的点加入队列2.如果在右边找到一个未匹配点，则找到可增广链3.如果在右边找到的是一个匹配的点，则看它是从左边哪个点匹配而来的，将那个点出发的所有右边点加入队列这么说还是不容易明白，看代码吧view plaincopy to clipboardprint?3.最佳匹配加权图中，权值最大的最大匹配KM算法：概念：f(v)是每个点的一个值，使得对任意u,v C V，f(u)+f(v)>=w[e u,v]集合H：一个边集，使得H中所有u,v满足f(u)+f(v)=w[e u,v]等价子图：G f(V,H)，标有f函数的G图理论：对于f和G f，如果有一个理想匹配集合M p，则M p最优。

最大权匹配KM算法
KM算法（Kuhn–Munkres算法，也称为匈牙利算法）是由Kuhn于
1955年和Munkres于1957年分别提出的，用于解决二分图最大匹配问题。

该算法的核心思想是基于匈牙利算法的增广路径，通过构建一个增广路径
来不断更新匹配，直到无法找到增广路径为止。

算法流程如下：
2.从G的每个未匹配顶点开始，通过增广路径将其标记为可增广点；
3.当存在增广路径时，将匹配的边进行反向操作，直到不存在增广路径；
4. 利用增广路径的反向操作可以修改lx和ly的值，使其满足特定
约束条件；
5.通过相等子图的扩展来实现增广路径的；
6.重复步骤3-5，直到不存在更多的增广路径；
7.返回找到的最大匹配。

具体实现时，对于增广路径的可以利用DFS或BFS等方法进行，当找
到一个增广路径时，通过反向操作修改匹配情况，并更新lx和ly的值。

同时，算法还可以使用增广路径来调整优化标号，以减少匹配时间。

KM算法是一种高效的解决最大权匹配问题的方法，其时间复杂度为
O(V^3)，其中V为图的顶点数。

算法的核心思想是利用二分图中的相等子
图来查找增广路径，并通过修改顶点的标号来实现最大匹配。

总之，最大权匹配KM算法是一个解决带权无向二分图最大匹配问题
的高效算法，通过不断寻找增广路径并调整顶点的标号来实现最大权匹配。

它的思想简单而有效，可以广泛应用于各种实际问题中。

km算法原理KM算法原理：带权二分图最大权完美匹配KM算法全称为Kuhn-Munkres算法，是一种求解带权二分图最大权完美匹配的算法。

该算法的时间复杂度为O(n^3)，相较于暴力枚举的O(n!)和网络流的O(n^4)，其效率更高。

我们来了解一下什么是带权二分图。

带权二分图是指一个无向图G=(V, E)，其中V可以划分为两个集合X和Y，使得X和Y内部的点没有边相连，而X和Y之间的点有边相连，并且每条边都有一个权值。

我们的目标是找到X到Y的最大权匹配。

KM算法的思路是不断尝试寻找增广路，并将其加入当前匹配中。

增广路是指从未匹配的点开始，经过一系列已匹配的点，最终到达另一个未匹配的点的路径。

如果当前匹配中不存在增广路，那么我们就找到了最大权匹配。

具体实现时，我们需要使用两个数组：lx和ly。

lx[i]表示左边第i个点的最大权值，ly[j]表示右边第j个点的最大权值。

初始时，我们将lx[i]=max{w[i][j]}，其中w[i][j]表示左边第i个点到右边第j个点的边权值，ly[j]=0。

然后我们不断进行匹配，直到没有增广路为止。

匹配的过程中，我们需要使用一个vis数组记录右边第j个点是否被访问过。

如果右边第j个点未被访问，我们就尝试匹配左边第i个点和右边第j个点，如果匹配成功，就更新lx[i]和ly[j]的值。

如果匹配失败，我们就需要尝试将当前匹配中的某个点切换到另一个点上，以获得更大的权值。

这个过程可以通过递归实现。

我们得到的匹配就是带权二分图的最大权完美匹配。

KM算法的时间复杂度为O(n^3)，空间复杂度为O(n^2)。

KM算法是一种高效的求解带权二分图最大权完美匹配的算法。

它的思路简单，实现也不难，但需要注意细节和边界条件。

在实际应用中，KM算法可以用于匹配问题、优化问题等方面。

图论中的二分图匹配问题及其算法设计思路二分图匹配问题是图论中的重要问题之一。

二分图是指一个图的顶点可以分为两个互斥的集合，并且图的边只能连接两个集合之间的顶点。

二分图匹配的目标是找到一个匹配，即找到一种对应关系，使得图中的所有顶点都能够与另一个集合中的顶点相连。

在实际应用中，二分图匹配有着广泛的应用。

比如在招聘网站中，求职者和企业可以被看作是一个二分图，通过匹配求职者和企业，可以使得求职者找到合适的工作岗位，企业找到合适的人才。

在网络流量调度中，可以将网络中的节点和链路看作一个二分图，通过匹配可以实现有效的数据传输。

那么如何解决二分图匹配问题呢？目前比较常用的算法有匈牙利算法和增广路径算法。

匈牙利算法，也称为增广路径算法，是解决二分图最大匹配问题的一种经典算法。

该算法从某一个未匹配的顶点开始，尝试去匹配其他的顶点。

如果当前顶点没有匹配的边，那么匈牙利算法会尝试寻找一个增广路径，即一条能够增加匹配数的路径。

当不存在增广路径时，匈牙利算法会返回当前匹配的结果。

增广路径算法是一个递归的过程。

首先，我们从一个未匹配的顶点开始，将其标记为已访问。

然后遍历与该顶点相连的所有边，如果边的另一个顶点没有被访问过，那么我们尝试去匹配这个顶点。

如果匹配成功，那么整个算法就结束了，返回当前的匹配结果。

如果匹配失败，我们需要尝试寻找另一个增广路径，这时我们会递归地调用增广路径算法，从当前的匹配边的另一个顶点开始。

增广路径算法的时间复杂度为O(V*E)，其中V是顶点数，E是边数。

在实际应用中，匈牙利算法已经被广泛应用，因为其算法简单易懂，同时具有较好的计算效率。

除了匈牙利算法，还有其他一些解决二分图匹配问题的算法，比如多项式时间的Hopcroft-Karp算法和Edmonds的算法。

这些算法在不同的应用场景中，可能有着更好的性能表现。

总结来说，二分图匹配问题在图论中具有重要的地位，它可以通过匈牙利算法等多种算法来解决。

在实际应用中，二分图匹配问题可以用于求职招聘、网络流量调度等领域。

二分图匹配算法总结 (by phoenixinter, Aug 2006)最近下决心要把二分图匹配部分的算法都搞搞清楚，努力了几天之后基本上搞定了，下面做一个这个专题的总结。

一、二分图最大匹配二分图最大匹配的经典匈牙利算法是由Edmonds在1965年提出的，算法的核心就是根据一个初始匹配不停的找增广路，直到没有增广路为止。

匈牙利算法的本质实际上和基于增广路特性的最大流算法还是相似的，只需要注意两点：（一）每个X节点都最多做一次增广路的起点；（二）如果一个Y节点已经匹配了，那么增广路到这儿的时候唯一的路径是走到Y节点的匹配点（可以回忆最大流算法中的后向边，这个时候后向边是可以增流的）。

找增广路的时候既可以采用dfs也可以采用bfs，两者都可以保证O(nm)的复杂度，因为每找一条增广路的复杂度是O(m)，而最多增广n次，dfs在实际实现中更加简短。

二、Hopcroft-Karp算法SRbGa很早就介绍过这个算法，它可以做到O(sqrt(n)*e)的时间复杂度，并且在实际使用中效果不错而且算法本身并不复杂。

Hopcroft-Karp算法是Hopcroft和Karp在1972年提出的，该算法的主要思想是在每次增广的时候不是找一条增广路而是同时找几条点不相交的最短增广路，形成极大增广路集，随后可以沿着这几条增广路同时进行增广。

可以证明在寻找增广路集的每一个阶段所寻找到的最短增广路都具有相等的长度，并且随着算法的进行最短增广路的长度是越来越长的，更进一步的分析可以证明最多只需要增广ceil(sqrt(n))次就可以得到最大匹配（证明在这里略去）。

因此现在的主要难度就是在O(e)的时间复杂度内找到极大最短增广路集，思路并不复杂，首先从所有X的未盖点进行BFS，BFS之后对每个X节点和Y节点维护距离标号，如果Y节点是未盖点那么就找到了一条最短增广路，BFS完之后就找到了最短增广路集，随后可以直接用DFS对所有允许弧(dist[y]=dist[x]+ 1，可以参见高流推进HLPP的实现)进行类似于匈牙利中寻找增广路的操作，这样就可以做到O(m)的复杂度。

km(kuhn-munkres)算法的具体表达KM算法，即Kuhn-Munkres算法（又称为匈牙利算法），是一种用于求解二分图最大权匹配问题的经典算法。

它由Eugene L. Lawler于1960年首次提出，后来由James Munkres在1957年独立发表，因此常称为Kuhn-Munkres算法。

二分图最大权匹配问题是指给定一个带权二分图，要求在图中选取权重之和最大的边集合，使得任意两条边不属于同一个顶点。

其中，带权二分图是指图的每条边都带有一个非负权重。

KM算法使用了两个关键的概念：交错树和相等子图。

交错树是指一个T=（S，P）的有向树，其中S是原二分图的所有顶点的集合，P是树中的边集合。

相等子图是指原二分图的一个子图，其中T中所有入树边的权重之和等于所有出树边的权重之和。

KM算法具体的步骤如下：1.初始化：将图中所有边的权重初始化为0，构建了一个初始的交错树T=（X，Y）（其中X，Y分别表示两个顶点集合）。

2.判断相等子图：对于T中的每个顶点x，如果存在一条满足lx+ly=W（其中lx是x在T中所有入树边的权重之和，ly是x在T中所有出树边的权重之和，W是x在原图G中的权重），则把x加入到相等子图中。

3.寻找未匹配节点：在相等子图中寻找未匹配节点，并标记为未父节点。

4.寻找增广路：如果存在未匹配节点，则从中选择一个起始节点，寻找一条与之交替出现的边构成的路径，使路径的最后一个边是一条与未匹配节点关联的边。

这样的路径称为增广路。

5.修改标号：对于相等子图中的每个顶点x，从已匹配节点中选择一个与之关联的顶点y，并计算d=min(lx+ly-w)（其中w是x和y之间的边的权重），为了使增广路更优，将T中所有x节点的入树边的权重减去d，将T中所有y节点的出树边的权重加上d。

6.更新交错树：将增广路中的所有边和T中的所有非树边进行调整，得到新的交错树。

7.重复步骤3-6，直到没有未匹配节点为止。

二分图的概念二分图又称作二部图，是图论中的一种特殊模型。

设G=(V, E)是一个无向图。

如果顶点集V可分割为两个互不相交的子集X和Y，并且图中每条边连接的两个顶点一个在X中，另一个在Y中，则称图G为二分图。

二分图的性质定理：当且仅当无向图G的每一个回路的次数均是偶数时，G才是一个二分图。

如果无回路，相当于任一回路的次数为0，故也视为二分图。

二分图的判定如果一个图是连通的，可以用如下的方法判定是否是二分图：在图中任选一顶点v，定义其距离标号为0，然后把它的邻接点的距离标号均设为1，接着把所有标号为1的邻接点均标号为2（如果该点未标号的话），如图所示，以此类推。

标号过程可以用一次BFS实现。

标号后，所有标号为奇数的点归为X部，标号为偶数的点归为Y部。

接下来，二分图的判定就是依次检查每条边，看两个端点是否是一个在X部，一个在Y部。

如果一个图不连通，则在每个连通块中作判定。

二分图匹配给定一个二分图G，在G的一个子图M中，M的边集{E}中的任意两条边都不依附于同一个顶点，则称M是一个匹配。

图中加粗的边是数量为2的匹配。

最大匹配选择边数最大的子图称为图的最大匹配问题(maximal matching problem)如果一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完全匹配，也称作完备匹配。

图中所示为一个最大匹配，但不是完全匹配。

增广路径增广路径的定义：设M为二分图G已匹配边的集合，若P是图G中一条连通两个未匹配顶点的路径（P的起点在X部，终点在Y部，反之亦可），并且属M的边和不属M的边(即已匹配和待匹配的边)在P上交替出现，则称P为相对于M的一条增广路径。

增广路径是一条“交错轨”。

也就是说, 它的第一条边是目前还没有参与匹配的,第二条边参与了匹配,第三条边没有..最后一条边没有参与匹配,并且起点和终点还没有被选择过，这样交错进行,显然P有奇数条边（为什么？）红边为三条已经匹配的边。

从X部一个未匹配的顶点x4开始，找一条路径：x4,y3,x2,y1,x1,y2x4,y3,x2,y1,x1,y2因为y2是Y部中未匹配的顶点，故所找路径是增广路径。

[二分图带权匹配与最佳匹配]什么是二分图的带权匹配？二分图的带权匹配就是求出一个匹配集合，使得集合中边的权值之和最大或最小。

而二分图的最佳匹配则一定为完备匹配，在此基础上，才要求匹配的边权值之和最大或最小。

二分图的带权匹配与最佳匹配不等价，也不互相包含。

我们可以使用KM算法实现求二分图的最佳匹配。

方法我不再赘述，可以参考tianyi的讲解。

KM算法可以实现为O(N^3)。

[KM算法的几种转化]KM算法是求最大权完备匹配，如果要求最小权完备匹配怎么办？方法很简单，只需将所有的边权值取其相反数，求最大权完备匹配，匹配的值再取相反数即可。

KM算法的运行要求是必须存在一个完备匹配，如果求一个最大权匹配(不一定完备)该如何办？依然很简单，把不存在的边权值赋为0。

KM算法求得的最大权匹配是边权值和最大，如果我想要边权之积最大，又怎样转化？还是不难办到，每条边权取自然对数，然后求最大和权匹配，求得的结果a再算出e^a就是最大积匹配。

至于精度问题则没有更好的办法了。

[求最小(大)权匹配的费用流建模方法]求最小(大)权匹配，可以用最小(大)费用最大流的方法。

和二分图最大匹配的构图方法类似，添加附加源S和附加汇T，从S向二分图X集合中每个顶点连接一条权值为0，容量为1的有向边，从Y集合中每个顶点向T也连接一条权值为0，容量为1的有向边。

然后把原有的边变成容量为1，权值不变的有向边。

求从S到T的最小(大)费用最大流，就能求得最小(大)权匹配。

上述建模求最大权匹配的方法求得的一定是最佳匹配(如果存在完备匹配)，因为S到X集合每条边全部满流。

如下图所示，最小费用最大流为2。

要求最大权匹配(不一定完备匹配)。

如下图，只需再引入一个顶点A，从X集合的每个顶点向A连接一条容量为1，权值为0的边，然后再由A向T连接一条权值为0，容量不小于|X|的边，求最大费用最大流，这时是100。

最小权匹配也类似，不过新加的边权要为一个极大值，大于所有已有边权值。

最大权匹配KM算法KM 算法（Kuhn–Munkres 算法）又被称为匈牙利算法或者二分图最佳匹配算法，是用来解决二分图最大权匹配问题的一种有效算法。

它的时间复杂度为 O(n^3)，其中 n 是二分图中的顶点数。

在二分图最大权匹配问题中，给定一个二分图，找到一种边的匹配方式，使得所有边的权重之和达到最大。

其中，二分图是一种图，其顶点可以分为两个不相交的集合U和V，并且图中的每条边都连接U和V中的两个顶点之一KM 算法的主要思想是通过设置两个顶标数组 lx 和 ly 来记录每个顶点的可行匹配权值。

算法的基本步骤如下：1. 初始化顶标数组 lx 和 ly 为 0。

2. 对于每个顶点 u 属于集合 U，找出 u 在集合 V 中的邻接顶点 v，计算顶点 u 和 v 之间的权值与当前顶标数组的差值 delta，如果 delta 大于顶点 v 的顶标，则更新顶标 lx[u] 为 delta。

3.从集合U中选择一个顶点u，对于该顶点u在集合V中的每个邻接顶点v，如果u和v当前没有匹配，则尝试将u和v进行匹配，并将顶点u标记为已匹配。

4. 如果存在未匹配的顶点，则尝试改变标号以寻找更大的匹配权重。

具体操作是分别减小顶标 lx[u] 和增加顶标 ly[v]，保持所有匹配的边不变。

5.重复步骤2-4，直到无法找到更大权重的匹配。

KM 算法的关键在于通过改变顶标数组 lx 和 ly，以及不断改变已匹配的顶点来寻找更大的权重匹配。

当顶标数组不再改变时，即找到了最大权匹配。

需要注意的是，KM算法只能解决二分图的最大权匹配，如果给定的图不是二分图，需要先进行二分图的判定。

此外，KM算法也可以用来解决最小权匹配问题，只需要将边的权重取相反数即可。

总结来说，KM算法通过设置顶标数组和不断改变匹配的顶点来寻找二分图的最大权匹配。

它是一种时间复杂度较低、效率较高的算法，有着广泛的应用场景，例如任务分配、资源分配等问题。

⼆分图匹配之最佳匹配——KM算法今天也⼤致学了下KM算法，⽤于求⼆分图匹配的最佳匹配。

何为最佳？我们能⽤匈⽛利算法对⼆分图进⾏最⼤匹配，但匹配的⽅式不唯⼀，如果我们假设每条边有权值，那么⼀定会存在⼀个最⼤权值的匹配情况，但对于KM算法的话这个情况有点特殊，这个匹配情况是要在完全匹配（就是各个点都能⼀⼀对应另⼀个点）情况下的前提。

⾃然，KM算法跟匈⽛利算法有相似之处。

其算法步骤如下：1.⽤邻接矩阵（或其他⽅法也⾏啦）来储存图，注意：如果只是想求最⼤权值匹配⽽不要求是完全匹配的话，请把各个不相连的边的权值设置为0。

2.运⽤贪⼼算法初始化标杆。

3.运⽤匈⽛利算法找到完备匹配。

4.如果找不到，则通过修改标杆，增加⼀些边。

5.重复3，4的步骤，直到完全匹配时可结束。

⼀⾔不合地冒出了个标杆？？标杆是什么？？？在解释这个问题之前，我们先来假设⼀个很简单的情况，⽤我们⼈类伟⼤的智能思维去思考思考。

如上的⼀个⼆分图，我们要求它的最⼤权值匹配（最佳匹配）我们可以思索思索⼆分图最佳匹配还是⼆分图匹配，所以跟和匈⽛利算法思路差不多⼆分图是特殊的⽹络流，最佳匹配相当于求最⼤（⼩）费⽤最⼤流，所以FF⽅法也能实现所以我们可以把这匈⽛利算法和FF⽅法结合起来FF⽅法⾥⾯，我们每次是找最长（短）路进⾏通流所以⼆分图匹配⾥⾯我们也找最⼤边进⾏连边!但是遇到某个点被匹配了两次怎么办？那就⽤匈⽛利算法进⾏更改匹配！这就是KM算法的思路了：尽量找最⼤的边进⾏连边，如果不能则换⼀条较⼤的。

所以，根据KM算法的思路，我们⼀开始要对边权值最⼤的进⾏连线，那问题就来了，我们如何让计算机知道该点对应的权值最⼤的边是哪⼀条？或许我们可以通过某种⽅式记录边的另⼀端点，但是呢，后⾯还要涉及改边，⼜要记录边权值总和，⽽这个记录端点⽅法似乎有点⿇烦，于是KM采⽤了⼀种⼗分巧妙的办法（也是KM算法思想的精髓）：添加标杆（顶标）是怎样⼦呢？我们对左边每个点Xi和右边每个点Yi添加标杆Cx和Cy。

二分图最大权匹配 KM算法KM算法的正确性基于以下定理：若由二分图中所有满足A[i]+B[i]=w[i][j]的边C（i，j）构成的子图（即相等子图）有完备匹配，那么这个完备匹配就是二分图的最大权匹配基本概念1.完备匹配设G=V1,V2,E为二分图，|V1|=|V2|,M为G中的一个最大匹配，且|M|=V1,则称M为V1到V2的完备匹配。

通俗的理解，就是把V1中所有的点都匹配完2.可行顶标对于左边的点设为LX[maxn]数组，右边的点设为LY[maxn]数组，w[i][j]表示 v[i] 到 v[j] 的权值3.相等子图相等子图为完备匹配中所有的匹配，即全部V1中的点和与V1中的点匹配的V2中的点，但是边只包含 LX[i]+LY[j]=W[i][j]的边4.最优完备匹配最优完备匹配就是在完备匹配的条件下求解权值最大或者最小，若由二分图中所有满足A[i]+B[i]=W[i][j]的边C（i，j）构成的相等子图有完备匹配，那么这个完备匹配就是二分图的最大权匹配因为对于二分图的任意一个匹配，如果它包含相等子图，那么它的边权和等于所有顶点的顶标和；如果它有边不包含于相等子图，那么它的边权和小于所有顶点的顶标和，所以相等子图的完备匹配，一定是二分图的最大权匹配。

5.交错树对V1中的一个顶点进行匹配的时候，所标记过的V1，V2中的点以及连线，形成一个树状的图KM算法原理1.基本原理该算法是通过给每个顶点一个标号(叫做顶标）来把求最大权匹配的问题转化为求完备匹配的问题。

设顶点V1的顶标lx[i]，V2顶点的顶标为LY[j],顶点V1的i与V2的j之间的边权为V(i,j)。

在算法执行的过程中，对于任一条边C(i,j)，LX[i]+LY[i]=V[i,j]始终成立2.基本流程（1）初始化时为了使 LX[i] + LY[j] = V [i,j]恒成立，将V1的点的标号记为与其相连的最大边权值，V2的点标号记为0 （2）用匈牙利算法在相等子图寻找完备匹配（3）若未找到完备匹配，则修改可行顶标的值，扩充相等子图（4）重复（2）（3）直到找到相等子图的完备匹配为止3.这里值得注意的是找完备匹配不难理解，主要是进行可行顶标的修改扩充相等子图朴素的实现方法：时间复杂度为O(n4)——需要找O(n)次增广路，每次增广最多需要修改O(n)次顶标，每次修改顶标时由于要枚举边来求d值，复杂度为O(n2)。