下载文档原格式
二分图的最大匹配完美匹配和匈牙利算法匈牙利算法是由匈牙利数学家Edmonds于1965年提出，因而得名。
匈牙利算法是基于Hall定理中充分性证明的思想，它是二部图匹配最常见的算法，该算法的核心就是寻找增广路径，它是一种用增广路径求二分图最大匹配的算法。
这篇文章讲无权二分图（unweighted bipartite graph）的最大匹配（maximum matching）和完美匹配（perfect matching），以及用于求解匹配的匈牙利算法（Hungarian Algorithm）；不讲带权二分图的最佳匹配。
二分图：简单来说，如果图中点可以被分为两组，并且使得所有边都跨越组的边界，则这就是一个二分图。
准确地说：把一个图的顶点划分为两个不相交集U 和V ，使得每一条边都分别连接U、V 中的顶点。
如果存在这样的划分，则此图为一个二分图。
二分图的一个等价定义是：不含有「含奇数条边的环」的图。
图 1 是一个二分图。
为了清晰，我们以后都把它画成图 2 的形式。
匹配：在图论中，一个「匹配」（matching）是一个边的集合，其中任意两条边都没有公共顶点。
例如，图3、图4 中红色的边就是图 2 的匹配。
我们定义匹配点、匹配边、未匹配点、非匹配边，它们的含义非常显然。
例如图 3 中1、4、5、7 为匹配点，其他顶点为未匹配点；1-5、4-7为匹配边，其他边为非匹配边。
最大匹配：一个图所有匹配中，所含匹配边数最多的匹配，称为这个图的最大匹配。
图 4 是一个最大匹配，它包含4 条匹配边。
完美匹配：如果一个图的某个匹配中，所有的顶点都是匹配点，那么它就是一个完美匹配。
图 4 是一个完美匹配。
显然，完美匹配一定是最大匹配（完美匹配的任何一个点都已经匹配，添加一条新的匹配边一定会与已有的匹配边冲突）。
但并非每个图都存在完美匹配。
举例来说：如下图所示，如果在某一对男孩和女孩之间存在相连的边，就意味着他们彼此喜欢。
是否可能让所有男孩和女孩两两配对，使得每对儿都互相喜欢呢？图论中，这就是完美匹配问题。
二分图匹配算法总结二分图匹配算法总结二分图最大匹配的匈牙利算法二分图是这样一个图，它的顶点可以分类两个集合X和Y，所有的边关联在两个顶点中，恰好一个属于集合Ｘ，另一个属于集合Ｙ。
最大匹配：图中包含边数最多的匹配称为图的最大匹配。
完美匹配：如果所有点都在匹配边上，称这个最大匹配是完美匹配。
最小覆盖：最小覆盖要求用最少的点（Ｘ集合或Ｙ集合的都行）让每条边都至少和其中一个点关联。
可以证明：最少的点（即覆盖数）＝最大匹配数最小路径覆盖：用尽量少的不相交简单路径覆盖有向无环图Ｇ的所有结点。
解决此类问题可以建立一个二分图模型。
把所有顶点i拆成两个：Ｘ结点集中的i和Y结点集中的i',如果有边i->j，则在二分图中引入边i->j'，设二分图最大匹配为m,则结果就是n-m。
最大独立集问题：在Ｎ个点的图G中选出m个点，使这m个点两两之间没有边．求m最大值．如果图Ｇ满足二分图条件，则可以用二分图匹配来做．最大独立集点数= N - 最大匹配数二分图最大匹配问题的匈牙利算法：算法思想：算法的思路是不停的找增广轨,并增加匹配的个数,增广轨顾名思义是指一条可以使匹配数变多的路径,在匹配问题中,增广轨的表现形式是一条"交错轨",也就是说这条由图的边组成的路径,它的第一条边是目前还没有参与匹配的,第二条边参与了匹配,第三条边没有..最后一条边没有参与匹配,并且始点和终点还没有被选择过.这样交错进行,显然他有奇数条边.那么对于这样一条路径,我们可以将第一条边改为已匹配,第二条边改为未匹配...以此类推.也就是将所有的边进行"反色",容易发现这样修改以后,匹配仍然是合法的,但是匹配数增加了一对.另外,单独的一条连接两个未匹配点的边显然也是交错轨.可以证明,当不能再找到增广轨时,就得到了一个最大匹配.这也就是匈牙利算法的思路.一、二分图最大匹配二分图最大匹配的经典匈牙利算法是由Edmonds在1965年提出的，算法的核心就是根据一个初始匹配不停的找增广路，直到没有增广路为止。
⼆分图匹配问题最⼤匹配以及相关结论多重匹配最⼤带权匹配带花树算法⼆分图匹配问题：做法：①匈⽛利算法，时间复杂度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部节点,那么应该⽤⽹络流来解决。
改进的km 算法流程-回复改进的KM 算法流程是一种经典的图论优化算法，用于解决二分图最大匹配问题。
在传统的KM 算法中，我们通过不断调整边权来寻找最大匹配，但该方法在大规模图中算法效率不高。
为了改进算法效率，我们将在本文中介绍一种改进的KM 算法流程。
一、引言1.1 背景在实际生活和工程问题中，二分图最大匹配问题是一个常见的优化问题。
例如，在稳定婚姻问题中，我们希望找到一种合理的匹配方式，使得每个人都能够与其伴侣过上幸福的生活。
在电子交易中，我们希望找到一种最优匹配，以最大化买家和卖家之间的交易量。
1.2 传统KM 算法的缺陷传统的KM 算法是一种不断调整边权的启发式算法。
每次迭代中，我们通过调整顶标和深度优先搜索来寻找更优的匹配。
然而，在处理大规模图时，该算法的时间复杂度较高。
为了改进算法效率，我们提出了一种改进的KM 算法流程。
二、改进的KM 算法流程2.1 初始化首先，我们需要初始化算法所需的数据结构和变量：- `graph`：表示二分图的邻接矩阵- `lx`、`ly`：分别表示左边和右边顶点的顶标- `mx`、`my`：分别表示左边和右边顶点的匹配点- `slack`：记录右边顶点在增广路径中的松弛量- `visited`：记录左边顶点是否被访问过2.2 改进的算法流程接下来，我们介绍改进的KM 算法的流程：- 步骤1：基于当前匹配，计算每个顶点的顶标。
我们将使用Dijkstra 算法来计算顶标。
首先，我们初始化顶标数组`lx` 和`ly` 为0。
然后，我们从未匹配的左边顶点开始，依次更新其邻居顶点的顶标。
- 步骤2：寻找增广路径。
我们使用深度优先搜索来寻找增广路径。
从未匹配的左边顶点开始，我们依次尝试匹配其邻居节点。
- 步骤3：调整匹配。
根据找到的增广路径，我们调整当前匹配。
如果增广路径为空，则算法结束，当前匹配即为最大匹配。
否则，我们根据增广路径的奇偶性来调整匹配。
具体来说，对于奇数步的顶点，我们反转匹配；对于偶数步的顶点，我们保持匹配不变。
改进的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的路径，那么就找到了一条增广路径。
第九讲二分图匹配问题一、问题设G=(V,{R})是一个无向图。
如顶点集V可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属两个不同的子集。
则称图G为二分图。
给定一个二分图G，在G的一个子图M中，M的边集{E}中的任意两条边都不依附于同一个顶点，则称M是一个匹配。
选择这样的边数最大的子集称为图的最大匹配问题(maximal matching problem)如果一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完全匹配，也称作完备匹配。
最大匹配在实际中有广泛的用处，求最大匹配的一种显而易见的算法是：先找出全部匹配，然后保留匹配数最多的。
即回溯法，但是这个算法的复杂度为边数的指数级函数。
因此，需要寻求一种更加高效的算法。
二、算法分析二分图的最大匹配有2种实现，网络流和匈牙利算法。
1.匈牙利算法是求解最大匹配的有效算法，该算法用到了增广路的定义(也称增广轨或交错轨)：若边集合P 是图G中一条连通两个未匹配顶点的路径，并且属M的边和不属M的边(即已匹配和待匹配的边)在P上交替出现，则称P为相对于M的一条增广路径。
2.由增广路径的定义可以推出下述三个结论：（1）. P的路径长度必定为奇数，第一条边和最后一条边都不属于M。
（2）. P经过“取反操作”（即非M中的边变为M中的边，原来M中的边去掉）可以得到一个更大的匹配M’。
（3）. M为G的最大匹配当且仅当不存在相对于M的增广路径。
3.从而可以得到求解最大匹配的匈牙利算法：(1)置M为空；(2)找出一条增广路径P，通过“取反操作”获得更大的匹配M’代替M；(3)重复(2)操作直到找不出增广路径为止；根据该算法，可以选择深搜或者广搜实现，下面给出易于实现的深度优先搜索（DFS）实现。
三、实现1. 匈牙利算法的算法轮廓bool寻找从k出发的对应项出的可增广路{while(j与k邻接){if(j不在增广路上){把j加入增广路;if(j是未盖点或者从j的对应项出发有可增广路)则从k的对应项出有可增广路,返回true;修改j的对应项为k;}}从k的对应项出没有可增广路,返回false;}2. 匈牙利算法流程3.代码int n, m, match[100]; //二分图的两个集合分别含有n和m个元素,match[i]存储集合m中的节点i在集合n 中的匹配节点,初值为-1。
二分图如果是没有权值的，求最大匹配。
则是用匈牙利算法求最大匹配。
如果带了权值，求最大或者最小权匹配，则必须用KM算法。
其实最大和最小权匹配都是一样的问题。
只要会求最大匹配，如果要求最小权匹配，则将权值取相反数，再把结果取相反数，那么最小权匹配就求出来了。
KM算法及其难理解。
看了几天还无头绪。
先拿上一直采用的KM算法模板，按照吉林大学的模板写的。
试试了好多次感觉都没有出错。
/******************************************************二分图最佳匹配（kuhn munkras 算法O(m*m*n)).邻接矩阵形式。
返回最佳匹配值，传入二分图大小m,n邻接矩阵mat ，表示权，match1,match2返回一个最佳匹配,为匹配顶点的match 值为-1，一定注意m<=n，否则循环无法终止，最小权匹配可将全职取相反数。
初始化：for(i=0;i<MAXN;i++)for(j=0;j<MAXN;j++) mat[i][j]=-inf;对于存在的边：mat[i][j]=val;//注意不能负值********************************************************/#include<string.h>#define MAXN 310#define inf 1000000000#define _clr(x) memset(x,-1,sizeof(int)*MAXN)int KM(int m,int n,int mat[][MAXN],int *match1,int *match2){int s[MAXN],t[MAXN],l1[MAXN],l2[MAXN];int p,q,i,j,k,ret=0;for(i=0;i<m;i++){l1[i]=-inf;for(j=0;j<n;j++)l1[i]=mat[i][j]>l1[i]?mat[i][j]:l1[i];if(l1[i]==-inf) return -1;}for(i=0;i<n;i++)l2[i]=0;_clr(match1);_clr(match2);for(i=0;i<m;i++){_clr(t);p=0;q=0;for(s[0]=i;p<=q&&match1[i]<0;p++){for(k=s[p],j=0;j<n&&match1[i]<0;j++){if(l1[k]+l2[j]==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;}}}}}if(match1[i]<0){i--;p=inf;for(k=0;k<=q;k++){for(j=0;j<n;j++){if(t[j]<0&&l1[s[k]]+l2[j]-mat[s[k]][j]<p)p=l1[s[k]]+l2[j]-mat[s[k]][j];}}for(j=0;j<n;j++)l2[j]+=t[j]<0?0:p;for(k=0;k<=q;k++)l1[s[k]]-=p;}}for(i=0;i<m;i++)ret+=mat[i][match1[i]];return ret;}下面是从网上的博客摘抄的一些零散的总结。
二分图最大权完美匹配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)了。
doc2。
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。
附代码：#include <cstdio>#include <memory.h>#include <algorithm> // 使用其中的min 函数using namespace std;const int MAX = 1024;int n; // X 的大小int weight [MAX] [MAX]; // X 到Y 的映射（权重）int lx [MAX], ly [MAX]; // 标号bool sx [MAX], sy [MAX]; // 是否被搜索过int match [MAX]; // Y(i) 与X(match [i]) 匹配// 初始化权重void init (int size);// 从X(u) 寻找增广道路，找到则返回truebool path (int u);// 参数maxsum 为true ，返回最大权匹配，否则最小权匹配int bestmatch (bool maxsum = true);void init (int size){// 根据实际情况，添加代码以初始化n = size;for (int j = 0; j < n; j ++)scanf ("%d", &weight [i] [j]);}bool path (int u){sx [u] = true;for (int v = 0; v < n; v ++)if (!sy [v] && lx[u] + ly [v] == weight [u] [v]){sy [v] = true;if (match [v] == -1 || path (match [v])){match [v] = u;return true;}}return false;}int bestmatch (bool maxsum){int i, j;if (!maxsum){for (i = 0; i < n; i ++)for (j = 0; j < n; j ++)weight [i] [j] = -weight [i] [j];}// 初始化标号for (i = 0; i < n; i ++){lx [i] = -0x1FFFFFFF;ly [i] = 0;if (lx [i] < weight [i] [j])lx [i] = weight [i] [j];}memset (match, -1, sizeof (match));for (int u = 0; u < n; u ++)while (1){memset (sx, 0, sizeof (sx));memset (sy, 0, sizeof (sy));if (path (u))break;// 修改标号int dx = 0x7FFFFFFF;for (i = 0; i < n; i ++)if (sx [i])for (j = 0; j < n; j ++)if(!sy [j])dx = min (lx[i] + ly [j] - weight [i] [j], dx);for (i = 0; i < n; i ++){if (sx [i])lx [i] -= dx;if (sy [i])ly [i] += dx;}}int sum = 0;for (i = 0; i < n; i ++)sum += weight [match [i]] [i];if (!maxsum){sum = -sum;for (j = 0; j < n; j ++)weight [i] [j] = -weight [i] [j]; // 如果需要保持weight [ ] [ ] 原来的值，这里需要将其还原}return sum;}int main(){int n;scanf ("%d", &n);init (n);int cost = bestmatch (true);printf ("%d ", cost);for (int i = 0; i < n; i ++){printf ("Y %d -> X %d ", i, match [i]);}return 0;}/*53 4 6 4 96 4 5 3 87 5 3 4 26 3 2 2 58 4 5 4 7//执行bestmatch (true) ，结果为29*//*57 6 4 6 14 65 7 23 5 7 6 84 7 8 8 52 6 5 6 3//执行bestmatch (false) ，结果为21*/doc3二分图匹配算法总结(by phoenixinter, Aug 2006)最近下决心要把二分图匹配部分的算法都搞搞清楚，努力了几天之后基本上搞定了，下面做一个这个专题的总结。
