下载文档原格式
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值了。
⼆分图匹配问题最⼤匹配以及相关结论多重匹配最⼤带权匹配带花树算法⼆分图匹配问题：做法：①匈⽛利算法，时间复杂度O(N*V)②Hopcroft-Karp，时间复杂度O(√N*V)相关结论：①最⼩顶点覆盖(könig定理) ⼆分图的最⼩顶点覆盖=最⼤匹配数②最⼩路径覆盖（不要求⼆分图）：在图中找⼀些路径，使之覆盖了图中的所有顶点，且任何⼀个顶点有且只有⼀条路径与之关 最⼩路径覆盖 = 顶点数 - 最⼤匹配配对于有向⽆环图，⾸先拆点，建成⼆分图再进⾏求解·最⼩不相交路径覆盖 建图⽅式:把⼀个的点V拆点成Vx和Vy，如果A连向B，那么就建⼀条Ax连向By的边。
图中有多少条路径，可以以⼀种⽅法得到，就是计算出度为0的点的个数。
如果知道这个就很容易得出这个结论了 ·最⼩相交路径覆盖 做法⾸先跑floyd，求出原图的传递闭包，然后⽤上述⽅法做即可③最⼩边覆盖最⼩边覆盖=图顶点-最⼤匹配⾸先⼀开始，假如⼀条边都不选的话，要覆盖所有的点就必须每个点都选⼀次，也就是n次，然后每选⼀条边就会减少1个，所以结论显⽽易见④最⼤独⽴集最⼤独⽴集=图顶点-最⼤匹配=最⼩边覆盖⼆分图的独⽴数等于顶点数减去最⼤匹配数，很显然的把最⼤匹配两端的点都从顶点集中去掉这个时候剩余的点是独⽴集，这是|V|-2*|M|，同时必然可以从每条匹配边的两端取⼀个点加⼊独⽴集并且保持其独⽴集性质。
⼆分图多重匹配( ⼀ ) 如果x部节点只对应⼀个y部节点,⽽y部节点可以对应多个x部节点,那么这种匹配可以⽤匈⽛利算法来解决解决的问题：⼀个y最多匹配cnt个x是否成⽴，要问⼀个y匹配⼈数最⼤的最⼩值可以⽤⼆分答案来做解决思路：根据匈⽛利算法的思想，这时的link[u]要变成link[u][i],表⽰与y[u]匹配好了的第i个点，⽤vlink[u]记录已经于u点匹配了的点的个数，对于x中的x[k],找到⼀个与他相连的y[i]后，同样判断匈⽛利算法中的两个条件是否成⽴，若满⾜第⼀个条件，直接将x[k]，y[i]匹配，否则，如果与y[i]所匹配的点已经达到了饱和，那么在所有与y[i]配合的点中选⼀个点，检查能否找到增⼴路，如果能，就让出位置让x[k]与y[i]匹配( ⼆ )如果x部节点可以匹配多个y部节点,y部节点可以同时匹配多个x部节点,那么应该⽤⽹络流来解决。
二分图：二分图是这样的一个图，它的顶点可以分为两个集合X和Y。
所有的边关联的两个顶点中，恰好一个属于集合X，一个属于集合Y。
二分图的匹配：给定一个二分图G，M为G边集的一个子集，如果M满足当中的任意两条边都不依附于同一个顶点，则称M是一个匹配。
二分图的最大匹配:二分图的所有匹配中包含边数最多的匹配称为图的最大匹配。
完美（完备）匹配：如果所有点都在匹配边上，称这个最大匹配是完美匹配。
最佳匹配：如果边上带权的话，找出权和最大的匹配叫做求最佳匹配。
增广路径：也称增广轨或交错轨。
若P是图G中一条连通两个未匹配顶点的路径，并且属最大匹配边集M的边和不属M的边(即已匹配和待匹配的边)在P上交替出现，则称P为相对于M的一条增广轨。
定义总是抽象的下面通过图来理解它。
图中的线段（2->3, 3->1, 1->4）便是上面所说的p路径，我们假定边（1,3）是以匹配的边，（2,3）（1,4）是未匹配的边，则边（4,1）边（1,3）和边（3,2）在路径p上交替的出现啦，那么p就是相对于M的一条增广轨，这样我们就可以用边1,4 和边2,3 来替换边1,3 那么以匹配的边集数量就可以加1,。
下面给出关于二分图最大匹配的三个定理1:最大匹配数+ 最大独立集= n + m2:二分图的最小覆盖数= 最大匹配数3:最小路径覆盖= 最大独立集最大独立集是指求一个二分图中最大的一个点集，该点集内的点互不相连。
最小顶点覆盖是指在二分图中，用最少的点，让所有的边至少和一个点有关联。
最小路径覆盖是指一个不含圈的有向图G 中，G的一个路径覆盖是一个其结点不相交的路径集合P，图中的每一个结点仅包含于P 中的某一条路径。
路径可以从任意结点开始和结束，且长度也为任意值，包括0.1求解二分图最大匹配的方法：●匈牙利算法（时间复杂度O(nm)）其思想是是通过不断的寻找增广轨实现最大匹配。
●转化为单位容量简单网络的最大流问题(本文不介绍)在二分图的基础上，加入源点s和汇点t，让s与每个X结点连一条边，每个Y结点和t连一条边，所有弧的容量为1。
最大权匹配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算法是一个解决带权无向二分图最大匹配问题
的高效算法，通过不断寻找增广路径并调整顶点的标号来实现最大权匹配。
它的思想简单而有效，可以广泛应用于各种实际问题中。
匈牙利匹配算法的原理匈牙利匹配算法（也被称为二分图匹配算法或者Kuhn-Munkres算法）是用于解决二分图最大匹配问题的经典算法。
该算法由匈牙利数学家Dénes Kőnig于1931年提出，并由James Munkres在1957年进行改进。
该算法的时间复杂度为O(V^3)，其中V是图的顶点数。
匹配问题定义：给定一个二分图G=(X,Y,E)，X和Y分别代表两个不相交的顶点集合，E表示连接X和Y的边集合。
图中的匹配是指一个边的集合M，其中任意两条边没有公共的顶点。
匹配的相关概念：1.可增广路径：在一个匹配中找到一条没有被占用的边，通过这条边可以将匹配中的边个数增加一个，即将不在匹配中的边添加进去。
2. 增广路径：一个可增广路径是一个交替序列P=v0e1v1e2v2...ekvk，其中v0属于X且不在匹配中，v1v2...vk属于Y且在匹配中，e1e2...ek在原图中的边。
3.增广轨：一个交替序列形如V0E1V1E2...EkVk，其中V0属于X且不在匹配中，V1V2...Vk属于Y且在匹配中，E1E2...Ek在原图中的边。
增广轨是一条路径的特例，它是一条从X到Y的交替序列。
1.初始时，所有的边都不在匹配中。
2.在X中选择一个点v0，如果v0已经在匹配中，则找到与v0相连的在Y中的顶点v1、如果v1不在匹配中，则(v0,v1)是可增广路径的第一条边。
3. 如果v1在匹配中，则找到与v1相连的在X中的顶点v2，判断v2是否在匹配中。
依此类推，直到找到一个不在匹配中的点vn。
4.此时，如果n是奇数，则(n-1)条边在匹配中，这意味着我们找到了一条增广路径。
如果n是偶数，则(n-1)条边在匹配中，需要进行进一步的处理。
5.如果n是偶数，则将匹配中的边和非匹配中的边进行颠倒，得到一个新的匹配。
6.对于颠倒后的匹配，我们再次从第2步开始，继续寻找增广路径。
7.重复步骤2到步骤6，直到找不到可增广路径为止，此时我们得到了最大匹配。
改进的km 算法流程-回复改进的KM算法流程引言KM算法，即Kuhn-Munkres算法，也被称为匈牙利算法，是一种用于解决二分图最大权匹配问题的经典算法。
它在应用中被广泛使用，例如在任务分配、资源分配、航线规划等领域。
然而，KM算法在处理大规模问题时存在效率低下的问题。
为了提高算法的性能，学者们不断进行改进和优化。
本文将介绍改进后的KM算法的流程，并逐步解释每个步骤的具体操作。
一、问题描述在介绍改进的KM算法之前，首先需要明确问题的描述。
给定一个二分图，其中左侧顶点集合为X，右侧顶点集合为Y，边权重矩阵为C。
目标是找到一个匹配M，使得M中所有边的权重之和最大。
二、改进算法的基本思路改进的KM算法主要通过两个步骤来提高效率：启发式初始化和优化的增广路径寻找。
1. 启发式初始化：将初始标号设置为最小权重值2. 优化的增广路径寻找：通过DFS（深度优先搜索）和BFS（广度优先搜索）寻找增广路径下面将详细介绍这两个步骤。
三、启发式初始化启发式初始化的目的是在算法初始阶段就为每个顶点设置一个初始标号，以便减少后续迭代中的计算量。
具体步骤如下：1. 初始化顶点集合X和Y的标号为0。
2. 对于每个左侧顶点x∈X，找到该顶点对应的最大权重，将该权重作为左侧顶点x的初始标号。
3. 更新右侧顶点y∈Y的标号为与它相连的左侧顶点的初始标号中的最大值。
四、优化的增广路径寻找优化的增广路径寻找是通过DFS和BFS结合的方式来寻找增广路径，其中DFS用于尽可能延伸已有的匹配集，而BFS用于寻找未被匹配的顶点。
1. 初始化路径集合P为空。
2. 对于每个未匹配的左侧顶点x∈X，将x添加到路径集合P中。
3. 对于路径集合P中的每个顶点u，如果u是未匹配的左侧顶点，则将u的相邻未匹配右侧顶点v添加到路径集合P中，并将v的前驱节点设置为u。
4. 如果路径集合P中存在一条从未匹配的左侧顶点x开始，以交替的形式经过已匹配的边和未匹配的边，并最终达到未匹配的右侧顶点y的路径，那么就找到了一条增广路径。
改进的KM算法流程KM算法（Kuhn-Munkres算法）是一种用于解决二分图最大匹配问题的经典算法，但是在实际应用中，由于数据量大、维度高等原因，传统的KM算法效率较低。
本文将针对KM算法进行改进，详细说明改进后的算法流程。
1. 问题定义- 最大匹配问题是指在一个二分图中，找到一个最大的匹配，使得图中的边数最大化，即找到尽可能多的边，使得每个顶点都与某条边相关联。
2. 原始KM算法流程回顾- 在原始KM算法中，首先需要初始化顶标和匹配数组，然后通过不断调整顶标和匹配数组来寻找增广路径，直到无法找到增广路径为止。
3. 改进思路- 我们可以通过优化顶标调整的策略，以及采用更高效的数据结构来加速算法的执行。
同时，可以引入并行计算来提高算法的并发性能。
4. 改进后的算法流程- 初始化顶标和匹配数组：与原始KM算法相同。
- 通过优化的顶标调整策略来寻找增广路径：可以采用更高效的寻找增广路径的方法，如Dijkstra算法等。
- 并行计算：利用多线程或分布式计算来加速算法的执行，提高算法的并发性能。
- 更新匹配数组：根据找到的增广路径来更新匹配数组。
- 判断终止条件：如果无法找到增广路径，算法终止，得到最大匹配。
5. 算法分析- 通过优化顶标调整策略和引入并行计算，改进后的KM算法在处理大规模数据时具有更高的效率和并发性能。
- 改进后的算法能够更快地找到最大匹配，并且在实际应用中具有更好的适用性和稳定性。
6. 实验与评估- 我们可以通过对比原始KM算法和改进后的KM算法在不同规模数据上的执行时间和匹配结果来评估改进后算法的效果。
- 通过实验结果的对比分析，可以验证改进后的KM算法在效率和性能上的提升。
7. 结论- 通过对KM算法的改进，我们能够更好地解决二分图最大匹配问题，提高算法的执行效率和并发性能，使其更适用于处理大规模数据和高维度问题。
通过以上流程，我们详细说明了改进的KM算法流程，包括问题定义、原始算法回顾、改进思路、改进后的算法流程、算法分析、实验与评估以及结论。
1、图论—匹配4。
1 二分图最大匹配(hungary邻接表)//二分图最大匹配,hungary算法,邻接表形式,复杂度O(m*e)//返回最大匹配数,传入二分图大小m,n和邻接表list(只需一边)//match1,match2返回一个最大匹配,未匹配顶点match值为-1#include <string.h>#define MAXN 310#define _clr(x) memset(x,0xff,sizeof(int)*MAXN)struct edge_t{int from,to;edge_t* next;};int hungary(int m,int n,edge_t* list[],int* match1,int* match2){int s[MAXN],t[MAXN],p,q,ret=0,i,j,k;edge_t* e;for (_clr(match1),_clr(match2),i=0;i<m;ret+=(match1[i++]>=0)) for (_clr(t),s[p=q=0]=i;p<=q&&match1[i]<0;p++)for (e=list[k=s[p]];e&&match1[i]<0;e=e->next)if (t[j=e->to]<0){s[++q]=match2[j],t[j]=k;if (s[q]<0)for (p=j;p>=0;j=p)match2[j]=k=t[j],p=match1[k],match1[k]=j;}return ret;}4。
2 二分图最大匹配(hungary邻接阵)//二分图最大匹配,hungary算法,邻接阵形式,复杂度O(m*m*n)//返回最大匹配数,传入二分图大小m,n和邻接阵mat,非零元素表示有边//match1,match2返回一个最大匹配,未匹配顶点match值为-1#include <string.h>#define MAXN 310#define _clr(x) memset(x,0xff,sizeof(int)*MAXN)int hungary(int m,int n,int mat[][MAXN],int* match1,int* match2){ int s[MAXN],t[MAXN],p,q,ret=0,i,j,k;for (_clr(match1),_clr(match2),i=0;i<m;ret+=(match1[i++]>=0))for (_clr(t),s[p=q=0]=i;p<=q&&match1[i]<0;p++)for (k=s[p],j=0;j<n&&match1[i]<0;j++)if (mat[k][j]&&t[j]<0){s[++q]=match2[j],t[j]=k;if (s[q]<0)for (p=j;p>=0;j=p)match2[j]=k=t[j],p=match1[k],match1[k]=j;}return ret;}4。
Kuhn-Munkres 算法Maigo 的 KM 算法讲解（的确精彩）KM 算法是通过给每个顶点一个标号（叫做顶标）来把求最大权匹配的问题转 化为求完备匹配的问题的。
设顶点 Xi 的顶标为 A[i]，顶点 Yi 的顶标为 B[i]，顶点 Xi 与 Yj 之间的边权为 w[i,j]。
在算法执行过程中 的任一时刻，对于任一条边(i,j)， A[i]+B[j]>=w[i,j]始终成立。
KM 算法的正确 性基于以下定理： * 若由二分图中所有满足 A[i]+B[j]=w[i,j]的边(i,j)构成的子图 （称做相等子 图）有完备匹配，那么这个完备匹配就是二分图的最大权匹配。
这个定理是显然的。
因为对于二分图的任意一个匹配，如果它包含于相 等子图，那么它的边权和等于所有顶点的顶标和；如果它有的边不包含于相 等子图，那么它的边权和小于所有顶点的顶标和。
所以相等子图的完备匹配 一定是二分图的最大权匹配。
初始时为了使 A[i]+B[j]>=w[i,j]恒成立，令 A[i]为所有与顶点 Xi 关联的边 的最大权，B[j]=0。
如果当前的相等子图没有完备匹配，就按下面的方法修改 顶标以使扩大相等子图，直到相等子图具有完备匹配为止。
我们求当前相等子图的完备匹配失败了，是因为对于某个 X 顶点，我们 找不到一条从它出发的交错路。
这时我们获得了一棵交错树，它的叶子结点 全部是 X 顶点。
现在我们把交错树中 X 顶点的顶标全都减小某个值 d，Y 顶 点的顶标全都增加同一个值 d，那么我们会发现：两端都在交错树中的边(i,j)，A[i]+B[j]的值没有变化。
也就是说，它原来属于 相等子图，现在仍属于相等子图。
两端都不在交错树中的边(i,j)，A[i]和 B[j]都没有变化。
也就是说，它原来属于 （或不属于）相等子图，现在仍属于（或不属于）相等子图。
X 端不在交错树中，Y 端在交错树中的边(i,j)，它的 A[i]+B[j]的值有所增大。
它原来不属于相等子图，现在仍不属于相等子图。
X 端在交错树中，Y 端不在交错树中的边(i,j)，它的 A[i]+B[j]的值有所减小。
也就说，它原来不属于相等子图，现在可能进入了相等子图，因而使相等子 图得到了扩大。
现在的问题就是求 d 值了。
为了使 A[i]+B[j]>=w[i,j]始终成立，且至少有 一条边进入相等子图，d 应该等于 min{A[i]+B[j]-w[i,j]|Xi 在交错树中，Yi 不在 交错树中}。
以上就是 KM 算法的基本思路。
但是朴素的实现方法，时间复杂度为 O(n4)——需要找 O(n)次增广路，每次增广最多需要修改 O(n)次顶标，每次 修改顶标时由于要枚举边来求 d 值，复杂度为 O(n2)。
实际上 KM 算法的复 杂度是可以做到 O(n3)的。
我们给每个 Y 顶点一个“松弛量”函数 slack，每次 开始找增广路时初始化为无穷大。
在寻找增广路的过程中，检查边(i,j)时，如 果它不在相等子图中， 则让 slack[j]变成原值与 A[i]+B[j]-w[i,j]的较小值。
这样， 在修改顶标时，取所有不在交错树中的 Y 顶点的 slack 值中的最小值作为 d 值即可。
但还要注意一点：修改顶标后，要把所有的 slack 值都减去 d。
二分图最大权完美匹配 KM 算法 好吧，这弄点正经的。
这次就写写大家肯定很久以前就搞出来的 KM。
我写这个是因为前几天整理模板的时候居然发现我的 KM 还是 O(n^4)的，虽 然实际运行效果大部分和 O(n^3)差不多，但是理论的上界仍然让我不爽，就 像 network simplex algorithm 一样。
先说一下 KM 的适用范围。
据我分析 KM 实际上可以对任意带权（无论 正负权）二分图求最大/最小权完美匹配，唯一的一个，也是最重要的一个要 求就是这个匹配必须是完美匹配，否则 KM 的正确性将无法得到保证。
这个 当了解了 KM 的正确性证明之后自然就会知道。
非完美的匹配的似乎必须祭 出 mincost maxflow 了。
然后就是 KM 的时间界。
这里略去 KM 的步骤不谈。
众所周知，KM 弄 不好就会写出 O(n^4)的算法， 而实际上是存在 O(n^3)的实现的。
那么 O(n^4) 究竟是慢在什么地方呢？这个就需要搞清楚 O(n^4)的 4 究竟是怎么来的。
每个点都需要作一次增广，所以有一个 n 的循环。
每个循环内部，每次 可能无法得到一条增广路，需要新加入一个 y 顶点，然后重新寻找增广路。
一次最少加进 1 个点，所以最多加入 n 次。
每次重新找一遍增广路 n^2，更 新距离标号需要扫描每一条边 n^2，所以迭加起来 O(n)*O(n)*O(n^2)，结果 自然就是 O(n^4)。
第一层和第二层循环似乎没有很好的方法可以把它搞掉，所以我们只能 从第三层，也就是每次的 O(n^2)入手。
这一层包括两个部分，一个是增广路 的 n^2， 一个是更新标号的 n^2， 需要将二者同时搞掉才能降低总共的复杂度。
注意更新标号之后有一个最重要的性质，那就是 原来存在的合法边仍然合 法，更新只是将不合法的边变得合法。
所以当我们找到一次交错树，没有增 广路之后，下次再寻找的时候完全没有必要重新开始，因为原先有的边更新 之后还有，所以完全可以接着上一次得到的交错树继续寻找。
那么应该从什 么地方继续号、开始搜索呢？很明显是那些新加进的点，也就是新进入的那 些 y 点。
这样虽然不知道每次更新标号会又扫描多少次，但是每条边最多也 就被扫描一次，然后被添加进交错树一次。
所以这一块，n 层循环总的复杂 度是 O(n^2)。
按照这样描述的话，用 dfs 似乎没有可以接着上一次找的方法， 所以只能用 bfs 来写增广路的搜索了。
然后就是重标号。
这一段实际上是由重新扫了一次边，然后对 x 在树中 而 y 不在的边进行侦测，然后重新标号。
想把这个搞掉似乎是有些困难，但 是我们先做的是增广路搜索然后才是标号，增广路搜索的时候不也是要扫边 么？要是能在 bfs 的时候记录一下什么信息，到时候直接取用不就好了？所 以，做法就是在 bfs 的时候，对于每个扫到的这种边，更新一下对应的 y 顶 点的标号， 这个标号的意义就是 y 点连接的所有这种边当中可松弛的最小值， 定义为 slack[y]。
然后每次更新的时候扫一下所有的 y，对于所有没在交错树 中的 y，找到最小 slack[y]，然后更新就可以了。
注意由于我们要接着上一次 进行 bfs，所以上一次算出来的标号也要留下来。
别忘了重标号之后每个 y 点 的 slack[y]也要同样更新，这样每次寻找标号并更新的复杂度就是 O(n)了，n 层重标号最多也就是 O(n^2)，然后 bfs 的 O(n^2)，增广的 O(n)，所以对于每 个点，想对匹配进行增广，复杂度就是 O(n^2)，n 个点每个点来一次自然就 是 O(n^3)了。
CODE:#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int size = 160; const int INF = 100000000; // 相对无穷大 bool map[size][size];// 二分图的相等子图, map[i][j] = true 代表 Xi 与 Yj 有边bool xckd[size], yckd[size]; // 标记在一次 DFS 中，Xi 与 Yi 是否在交错树上int match[size];// 保存匹配信息，其中 i 为 Y 中的顶点标号，match[i]为 X 中顶点标号bool DFS(int, const int); void KM_Perfect_Match(const int n, const int edge[][size]) { int i, j; int lx[size], ly[size]; // KM 算法中 Xi 与 Yi 的标号 for(i = 0; i < n; i++) { lx[i] = -INF; ly[i] = 0; for(j = 0; j < n; j++) { lx[i] = max(lx[i], edge[i][j]); } } bool perfect = false; false while(!perfect) {// 初始化邻接矩阵for(i = 0; i < n; i++) { for(j = 0; j < n; j++) { if(lx[i]+ly[j] == edge[i][j]) map[i][j] = true true; else map[i][j] = false false; } }// 匹配过程int live = 0; memset(match, -1, sizeof(match)); for(i = 0; i < n; i++) { memset(xckd, false sizeof(xckd)); false,memset(yckd, false sizeof(yckd)); false, if(DFS(i, n)) live++; else { xckd[i] = true true; break; break } } if(live == n) perfect = true true; else {// 修改标号过程int ex = INF; for(i = 0; i < n; i++) { for(j = 0; xckd[i] && j < n; j++) { if(!yckd[j]) ex = min(ex, lx[i]+ly[j]-edge[i][j]); } } for(i = 0; i < n; i++) { if(xckd[i]) lx[i] -= ex; if(yckd[i]) ly[i] += ex; } } } }// 此函数用来寻找是否有以 Xp 为起点的增广路径，返回值为是否含有增广路bool DFS(int p, const int n) { int i; for(i = 0; i < n; i++) { if(!yckd[i] && map[p][i]) { yckd[i] = true true; int t = match[i]; match[i] = p; if(t == -1 || DFS(t, n)) { return true true; } match[i] = t; if(t != -1) xckd[t] = true true; } } return false false; }int main() { int n, edge[size][size]; // edge[i][j]为连接 Xi 与 Yj 的边的权值 int i;/*************************************************** * 在此处要做的工作 : * 读取二分图每两点间边的权并保存在 edge[][]中, * 若 X 与 Y 数目不等，应添加配合的顶点 * 保存二分图中 X 与 Y 的顶点数 n,若上一步不等应保 * 存添加顶点完毕后的 n ***************************************************/KM_Perfect_Match(n, edge); int cost = 0; for(i = 0; i < n; i++) { cost += edge[match[i]][i]; }// cost 为最大匹配的总和, match[]中保存匹配信息return 0; }另附 O(N^3)的算法代码:#include <cstdio> #include <queue> #include <algorithm> using namespace std; const int N = 128; const int INF = 1 << 28; class Graph { private: bool xckd[N], yckd[N]; int n, edge[N][N], xmate[N], ymate[N]; int lx[N], ly[N], slack[N], prev[N]; queue<int> Q; bool bfs(); void agument(int);public: bool make(); int KMMatch(); }; bool Graph::make() { int house[N], child[N], h, w, cn = 0; char line[N]; scanf("%d %d", &h, &w); if(w == 0) return false false; scanf("\n"); n = 0; \ for(int i = 0; i < h; i++) { gets(line); for(int j = 0; line[j] != 0; j++) { if(line[j] == 'H') house[n++] = i * N + j; if(line[j] == 'm') child[cn++] = i * N + j; } } for(int i = 0; i < n; i++) { int cr = child[i] / N, cc = child[i] % N; for(int j = 0; j < n; j++) { int hr = house[j] / N, hc = house[j] % N; edge[i][j] = -abs(cr-hr) - abs(cc-hc); } } return true true; } bool Graph::bfs() { while(!Q.empty()) { int p = Q.front(), u = p>>1; Q.pop(); if(p&1) { if(ymate[u] == -1) { agument(u); return true } true; else { xckd[ymate[u]] = true Q.push(ymate[u]<<1); } true; } else { for(int i = 0; i < n; i++) if(yckd[i]) continue; else if(lx[u]+ly[i] != edge[u][i]) { int ex = lx[u]+ly[i]-edge[u][i]; if(slack[i] > ex) { slack[i] = ex; prev[i] = u; } } else { yckd[i] = true prev[i] = u; true; Q.push((i<<1)|1); } }} return false false; } void Graph::agument(int u) { while(u != -1) { int pv = xmate[prev[u]]; ymate[u] = prev[u]; xmate[prev[u]] = u; u = pv; } } int Graph::KMMatch() { memset(ly, 0, sizeof(ly)); for(int i = 0; i < n; i++) { lx[i] = -INF; for(int j = 0; j < n; j++) lx[i] >?= edge[i][j]; } memset(xmate, -1, sizeof(xmate)); memset(ymate, -1, sizeof(ymate)); bool agu = true true; for(int mn = 0; mn < n; mn++) { if(agu) { memset(xckd, false sizeof(xckd)); false, memset(yckd, false sizeof(yckd)); false, for(int i = 0; i < n; i++) slack[i] = INF; while(!Q.empty()) Q.pop(); xckd[mn] = true Q.push(mn<<1); true; } if(bfs()) { agu = true continue; } true; int ex = INF; mn--; agu = false false; for(int i = 0; i < n; i++) if(!yckd[i]) ex <?= slack[i]; for(int i = 0; i < n; i++) { if(xckd[i]) lx[i] -= ex; if(yckd[i]) ly[i] += ex; slack[i] -= ex; } for(int i = 0; i < n; i++) if(!yckd[i] && slack[i] == 0) { yckd[i] = true true; Q.push((i<<1)|1); } } int cost = 0; for(int i = 0; i < n; i++) cost += edge[i][xmate[i]]; return cost;} int main() { Graph g; while(g.make()) printf("%d\n", -g.KMMatch()); \ return 0; }二分图匹配----基于匈牙利算法和 KM 算法 2007-09-19 16:54 设 G=(V,{R})是 一个无向图。
