用匈牙利算法求二分图的最大匹配

最佳重分配匈牙利算法最佳重分配匈牙利算法，也叫作匈牙利算法，是一种常用于解决二分图最大匹配问题的算法。

本文将介绍最佳重分配匈牙利算法的定义、原理、实现和应用。

一、算法定义最佳重分配匈牙利算法是一种寻找二分图最大匹配的算法，其基本思想是在尽可能增大匹配的前提下，找到每个左部点的最优匹配。

此算法能够有效应对利用贪心或DFS算法求得的最大匹配值较小的情况。

二、算法原理最佳重分配匈牙利算法是一个基于DFS搜索的寻找最大匹配的算法。

它的基本思路是从左边开始枚举每一个左部点，在右边的匹配点中找到最合适的点。

若最后所有的左部点都能找到匹配的右部点，则此时为最大匹配。

而如果出现找不到匹配点的情况，就需要对已经匹配的边进行重分配。

同时，算法也支持权重匹配，即将边的权重加入到选取匹配点的决策中，从而更准确地匹配。

三、算法实现最佳重分配匈牙利算法实现过程主要由以下几个步骤组成：1.从左边第一个点开始，寻找与其最优匹配的右部点，就是尝试将这个左部点与右部图的所有未被匹配过的点进行匹配，其中匹配的条件是要满足没有与其他左部点有相同的匹配。

2.如果找到一个匹配的右部点，那么将这个左部点和右部点建立匹配关系，并将右部点状态设置为已匹配。

3.如果没有找到合适的右部点，就要进行匹配重分配。

首先，将已经进行了匹配而且在重分配环中的所有点按照交替方式重新相连，形成一个环-链数据结构；同时，计算出这个环-链中权重最小的边的权重，然后将环-链上的奇数边权的点减去该最小值，偶数边的点加上该最小值。

最后，通过交替路径来更新匹配。

4.根据已经匹配的点的数量，决定是否需要继续匹配，若所有的左部点都找到了匹配的右部点，则证明达到了最大匹配。

四、算法应用最佳重分配匈牙利算法在实际应用中有着广泛的应用场景，主要用于解决二分图最大匹配问题。

例如在对学生和导师之间进行匹配、对工人和工作之间进行匹配时，就可以使用该算法来解决问题。

总体来说，最佳重分配匈牙利算法具有高效、简洁、易于实现和适用于多种场景的优点。

匈⽛利算法解决⼆分图最⼤匹配预备知识 匈⽛利算法是由匈⽛利数学家Edmonds于1965年提出，因⽽得名。

匈⽛利算法是基于Hall定理中充分性证明的思想，它是⼆分图匹配最常见的算法，该算法的核⼼就是寻找增⼴路径，它是⼀种⽤增⼴路径求⼆分图最⼤匹配的算法。

⼆分图 ⼆分图⼜称作⼆部图，是图论中的⼀种特殊模型。

设G=(V,E)是⼀个⽆向图，如果顶点V可分割为两个互不相交的⼦集(A，B)，并且图中的每条边（i，j）所关联的两个顶点 i 和 j 分别属于这两个不同的顶点集(i in A，j in B)，则称图G为⼀个⼆分图。

匹配 在图论中，⼀个图是⼀个匹配（或称独⽴边集）是指这个图之中，任意两条边都没有公共的顶点。

这时每个顶点都⾄多连出⼀条边，⽽每⼀条边都将⼀对顶点相匹配。

例如，图3、图4中红⾊的边就是图2的匹配。

图3中1、4、5、7为匹配点，其他顶点为⾮匹配点，1-5、4-7为匹配边，其他边为⾮匹配边。

最⼤匹配 ⼀个图所有匹配中，所含匹配边数最多的匹配，称为这个图的最⼤匹配。

图 4 是⼀个最⼤匹配，它包含 4 条匹配边。

任意图中，极⼤匹配的边数不少于最⼤匹配的边数的⼀半。

完美匹配 如果⼀个图的某个匹配中，所有的顶点都是匹配点，那么它就是⼀个完美匹配。

显然，完美匹配⼀定是最⼤匹配，但并⾮每个图都存在完美匹配。

最⼤匹配数：最⼤匹配的匹配边的数⽬。

最⼩点覆盖数：选取最少的点，使任意⼀条边⾄少有⼀个端点被选择。

最⼤独⽴数：选取最多的点，使任意所选两点均不相连。

最⼩路径覆盖数：对于⼀个DAG（有向⽆环图），选取最少条路径，使得每个顶点属于且仅属于⼀条路径，路径长可以为0（即单个点）定理1：Konig定理——最⼤匹配数 = 最⼩点覆盖数定理2：最⼤匹配数 = 最⼤独⽴数定理3：最⼩路径覆盖数 = 顶点数 - 最⼤匹配数匈⽛利算法例⼦ 为了便于理解，选取了dalao博客⾥找妹⼦的例⼦： 通过数代⼈的努⼒，你终于赶上了剩男剩⼥的⼤潮，假设你是⼀位光荣的新世纪媒⼈，在你的⼿上有N个剩男，M个剩⼥，每个⼈都可能对多名异性有好感（惊讶，-_-||暂时不考虑特殊的性取向） 如果⼀对男⼥互有好感，那么你就可以把这⼀对撮合在⼀起，现在让我们⽆视掉所有的单相思（好忧伤的感觉，快哭了），你拥有的⼤概就是下⾯这样⼀张关系图，每⼀条连线都表⽰互有好感。

匈牙利算法基于的原理匈牙利算法是一种解决二分图最大匹配的算法。

所谓二分图，是指一个图的顶点集可以分为两个互不相交的子集U、V，并且图中的每条边的一个端点属于U，另一个端点属于V。

最大匹配是指在二分图中找到一个由最多边组成的子图，使得任意两条边都没有共同的顶点。

首先，将所有的顶点标记为未匹配状态。

然后，从未匹配顶点开始，逐步增加匹配边。

在增加匹配边的过程中，如果可以找到增广路径，就将这条路径上的匹配边翻转，从而增加匹配数目。

重复这个过程，直到没有增广路径可找到为止。

具体步骤如下：1.选取一个未匹配顶点u，将其标记为已匹配状态。

2.对于u的每个邻居节点v，如果v是未匹配的，或者可以通过v的已匹配节点找到更长的增广路径，那么将v标记为已匹配状态，并将u与v匹配。

3.如果v已经是已匹配的，但是可以通过v的已匹配节点找到更长的增广路径，那么将u与v匹配，同时将原来与v匹配的节点转变为未匹配状态，并将u标记为已匹配状态。

4.重复上述步骤，直到所有节点均被匹配。

匈牙利算法的核心在于寻找增广路径的过程。

为了避免重复增广路径，一种常用的方法是采用深度优先。

通过深度优先，可以找到从未匹配节点u到已匹配节点v的一条最长增广路径。

在深度优先的过程中，需要借助一个辅助数组match[]来记录节点的匹配状态。

总结起来，匈牙利算法基于深度优先和增广路径的概念来寻找二分图的最大匹配。

其原理是通过逐步增加匹配边，找到增广路径来增加匹配数目。

通过标记节点的匹配状态，并通过深度优先来寻找增广路径，从而得到最大匹配。

设G=(V,{R})是一个无向图。

如顶点集V可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属两个不同的子集。

则称图G为二分图。

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

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

最大匹配在实际中有广泛的用处，求最大匹配的一种显而易见的算法是：先找出全部匹配，然后保留匹配数最多的。

但是这个算法的复杂度为边数的指数级函数。

因此，需要寻求一种更加高效的算法。

匈牙利算法是求解最大匹配的有效算法，该算法用到了增广路的定义(也称增广轨或交错轨)：若P是图G中一条连通两个未匹配顶点的路径，并且属M的边和不属M的边(即已匹配和待匹配的边)在P上交替出现，则称P为相对于M 的一条增广路径。

由增广路径的定义可以推出下述三个结论：v 1. P的路径长度必定为奇数，第一条边和最后一条边都不属于M。

v 2. P经过取反操作（即非M中的边变为M中的边，原来M中的边去掉）可以得到一个更大的匹配M’。

v 3. M为G的最大匹配当且仅当不存在相对于M的增广路径。

从而可以得到求解最大匹配的匈牙利算法：v(1)置M为空v(2)找出一条增广路径P，通过取反操作获得更大的匹配M’代替Mv(3)重复(2)操作直到找不出增广路径为止根据该算法，我选用dfs (深度优先搜索)实现。

程序清单如下：int match[i] //存储集合m中的节点i在集合n中的匹配节点,初值为-1。

int n,m,match[100]; //二分图的两个集合分别含有n和m个元素。

bool visit[100],map[100][100]; //map存储邻接矩阵。

bool dfs(int k){int t;for(int i = 0; i < m; i++)if(map[k][i] && !visit[i]){visit[i] = true;t = match[i];match[i] = k; //路径取反操作。

python实现匈⽛利算法求解⼆分图最⼤匹配重点：理解和取反1. 匈⽛利算法求解⽬标：找到⼆分图的最⼤匹配整体思路：每⼀步寻找⼀条增⼴路径，取反2. 关键步骤⼆分图的顶点分为左边点集X和右边点集Y，假定遍历的点集是X。

对于每⼀次迭代的点x_i，1. 搜索增⼴路径：遍历x_i的邻接节点y_j1. 如果y_j未匹配，则找到增⼴路2. 如果y_j已匹配，则寻找y_j的匹配节点的增⼴路径（深搜或者⼴搜）2. 取反：把增⼴路径中的已经匹配边改成未匹配；未匹配的改成匹配3. python代码算法输⼊为字典形式的特殊邻接表。

特殊之处在于字典的键和值的顶点分别属于⼆分图的左右点集合。

深度搜索增⼴路径函数的参数中的visited_set的作⽤是避免重复访问。

# 匈⽛利算法（dfs）class Hungarian:def search_extend_path(self, l_node, adjoin_map, l_match, r_match, visited_set):'''深度搜索增⼴路径'''for r_node in adjoin_map[l_node]: # 邻接节点if r_node not in r_match.keys(): # 情况1：未匹配, 则找到增⼴路径，取反l_match[l_node] = r_noder_match[r_node] = l_nodereturn Trueelse: # 情况2：　已匹配next_l_node = r_match[r_node]if next_l_node not in visited_set:visited_set.add(next_l_node)if self.search_extend_path(next_l_node, adjoin_map, l_match, r_match, visited_set): # 找到增⼴路径，取反l_match[l_node] = r_noder_match[r_node] = l_nodereturn Truereturn Falsedef run(self, adjoin_map):''':param adjoin_map: {x_i: [y_j, y_k]}:return:'''l_match, r_match = {}, {} # 存放匹配for lNode in adjoin_map.keys():self.search_extend_path(lNode, adjoin_map, l_match, r_match, set())return l_match。

最大二分图匹配（匈牙利算法）二分图指的是这样一种图：其所有的顶点分成两个集合M和N，其中M或N中任意两个在同一集合中的点都不相连。

二分图匹配是指求出一组边，其中的顶点分别在两个集合中，并且任意两条边都没有相同的顶点，这组边叫做二分图的匹配，而所能得到的最大的边的个数，叫做最大匹配。

计算二分图的算法有网络流算法和匈牙利算法（目前就知道这两种），其中匈牙利算法是比较巧妙的，具体过程如下（转自组合数学）：令g=（x,*,y）是一个二分图，其中x={x1,x2...},y={y1,y2,....}.令m为g中的任意匹配。

1。

将x的所有不与m的边关联的顶点表上￥，并称所有的顶点为未扫描的。

转到2。

2。

如果在上一步没有新的标记加到x的顶点上，则停，否则，转33。

当存在x被标记但未被扫描的顶点时，选择一个被标记但未被扫描的x的顶点，比如xi，用（xi）标记y 的所有顶点，这些顶点被不属于m且尚未标记的边连到xi。

现在顶点xi 是被扫描的。

如果不存在被标记但未被扫描的顶点，转4。

4。

如果在步骤3没有新的标记被标记到y的顶点上，则停，否则转5。

5。

当存在y被标记但未被扫描的顶点时。

选择y的一个被标记但未被扫描的顶点，比如yj，用（yj）标记x的顶点，这些顶点被属于m且尚未标记的边连到yj。

现在，顶点yj是被扫描的。

如果不存在被标记但未被扫描的顶点则转道2。

由于每一个顶点最多被标记一次且由于每一个顶点最多被扫描一次，本匹配算法在有限步内终止。

代码实现：bfs过程：#include<stdio.h>#include<string.h>main(){bool map[100][300];inti,i1,i2,num,num1,que[300],cou,stu,match1[100],match2[300],pqu e,p1,now,prev[300],n;scanf("%d",&n);for(i=0;i<n;i++){scanf("%d%d",&cou,&stu);memset(map,0,sizeof(map));for(i1=0;i1<cou;i1++){scanf("%d",&num);for(i2=0;i2<num;i2++){scanf("%d",&num1);map[i1][num1-1]=true;}}num=0;memset(match1,int(-1),sizeof(match1)); memset(match2,int(-1),sizeof(match2)); for(i1=0;i1<cou;i1++){p1=0;pque=0;for(i2=0;i2<stu;i2++){if(map[i1][i2]){prev[i2]=-1;que[pque++]=i2;}elseprev[i2]=-2;}while(p1<pque){now=que[p1];if(match2[now]==-1)break;p1++;for(i2=0;i2<stu;i2++){if(prev[i2]==-2&&map[match2[now]][i2]){prev[i2]=now;que[pque++]=i2;}}}if(p1==pque)continue;while(prev[now]>=0){match1[match2[prev[now]]]=now; match2[now]=match2[prev[now]]; now=prev[now];}match2[now]=i1;match1[i1]=now;num++;}if(num==cou)printf("YES\n");elseprintf("NO\n");}}dfs实现过程：#include<stdio.h>#include<string.h>#define MAX 100bool map[MAX][MAX],searched[MAX]; int prev[MAX],m,n;bool dfs(int data){int i,temp;for(i=0;i<m;i++){if(map[data][i]&&!searched[i]){searched[i]=true;temp=prev[i];prev[i]=data;if(temp==-1||dfs(temp))return true;prev[i]=temp;}}return false;}main(){int num,i,k,temp1,temp2,job;while(scanf("%d",&n)!=EOF&&n!=0) {scanf("%d%d",&m,&k);memset(map,0,sizeof(map));memset(prev,int(-1),sizeof(prev)); memset(searched,0,sizeof(searched));for(i=0;i<k;i++){scanf("%d%d%d",&job,&temp1,&temp2); if(temp1!=0&&temp2!=0)map[temp1][temp2]=true;}num=0;for(i=0;i<n;i++){memset(searched,0,sizeof(searched)); dfs(i);}for(i=0;i<m;i++){if(prev[i]!=-1)num++;}printf("%d\n",num);}}。

数学建模匈牙利算法
【最新版】
目录
一、匈牙利算法的概念与基本原理
二、匈牙利算法的应用实例
三、匈牙利算法的优缺点
正文
一、匈牙利算法的概念与基本原理
匈牙利算法（Hungarian algorithm）是一种求解二分图最大匹配问题的算法，由匈牙利数学家 Mátyásovszky 于 1937 年首次提出。

该算法的基本思想是：通过不断循环寻找图中的偶数长度路径，并将路径中的顶点依次匹配，直到找不到这样的路径为止。

此时，图中的所有顶点都已匹配，即得到了二分图的最大匹配。

二、匈牙利算法的应用实例
匈牙利算法广泛应用于任务分配、资源调度、数据融合等领域。

下面举一个简单的例子来说明匈牙利算法的应用。

假设有 5 个工人和 8 个任务，每个工人完成不同任务的效率不同。

我们需要为每个任务分配一个工人，使得总效率最大。

可以用一个二分图来表示这个问题，其中顶点分为两类：工人和任务。

边表示任务与工人之间的效率关系。

匈牙利算法可以用来求解这个问题，找到最优的任务分配方案。

三、匈牙利算法的优缺点
匈牙利算法的优点是简单、高效，可以解决二分图的最大匹配问题。

然而，它也存在一些缺点：
1.匈牙利算法只能解决无向图的匹配问题，对于有向图，需要将其转
换为无向图才能使用匈牙利算法。

2.当图中存在环时，匈牙利算法无法找到最大匹配。

这时需要使用其他算法，如 Euclidean algorithm（欧几里得算法）来解决。

3.匈牙利算法在实际应用中可能存在数值稳定性问题，即在计算过程中可能出现精度误差。

⼆分图最⼤匹配总结⼆分图匹配（匈⽛利算法）1。

⼀个⼆分图中的最⼤匹配数等于这个图中的最⼩点覆盖数König定理是⼀个⼆分图中很重要的定理，它的意思是，⼀个⼆分图中的最⼤匹配数等于这个图中的最⼩点覆盖数。

如果你还不知道什么是最⼩点覆盖，我也在这⾥说⼀下：假如选了⼀个点就相当于覆盖了以它为端点的所有边，你需要选择最少的点来覆盖所有的边。

2。

最⼩路径覆盖=最⼩路径覆盖＝｜G｜－最⼤匹配数在⼀个N*N的有向图中，路径覆盖就是在图中找⼀些路经，使之覆盖了图中的所有顶点，且任何⼀个顶点有且只有⼀条路径与之关联；（如果把这些路径中的每条路径从它的起始点⾛到它的终点，那么恰好可以经过图中的每个顶点⼀次且仅⼀次）；如果不考虑图中存在回路，那么每每条路径就是⼀个弱连通⼦集．由上⾯可以得出：1.⼀个单独的顶点是⼀条路径；2.如果存在⼀路径p1,p2,......pk，其中p1 为起点，pk为终点，那么在覆盖图中，顶点p1,p2,......pk不再与其它的顶点之间存在有向边．最⼩路径覆盖就是找出最⼩的路径条数，使之成为G的⼀个路径覆盖．路径覆盖与⼆分图匹配的关系：最⼩路径覆盖＝｜G｜－最⼤匹配数；3。

⼆分图最⼤独⽴集=顶点数-⼆分图最⼤匹配独⽴集：图中任意两个顶点都不相连的顶点集合。

⼆分图模板：模板⼀：匈⽛利算法/* **************************************************************************//⼆分图匹配（匈⽛利算法的DFS实现）//初始化：g[][]两边顶点的划分情况//建⽴g[i][j]表⽰i->j的有向边就可以了，是左边向右边的匹配//g没有边相连则初始化为0//uN是匹配左边的顶点数，vN是匹配右边的顶点数//调⽤：res=hungary();输出最⼤匹配数//优点：适⽤于稠密图，DFS找增⼴路，实现简洁易于理解//时间复杂度:O(VE)//***************************************************************************///顶点编号从0开始的const int MAXN=510;int uN,vN;//u,v数⽬int g[MAXN][MAXN];int linker[MAXN];bool used[MAXN];bool dfs(int u)//从左边开始找增⼴路径{int v;for(v=0;v<vN;v++)//这个顶点编号从0开始，若要从1开始需要修改if(g[u][v]&&!used[v]){used[v]=true;if(linker[v]==-1||dfs(linker[v])){//找增⼴路，反向linker[v]=u;return true;}}return false;//这个不要忘了，经常忘记这句}int hungary(){int res=0;int u;memset(linker,-1,sizeof(linker));for(u=0;u<uN;u++){memset(used,0,sizeof(used));if(dfs(u)) res++;}return res;}//******************************************************************************/模板⼆： Hopcroft-Carp算法这个算法⽐匈⽛利算法的时间复杂度要⼩，⼤数据可以采⽤这个算法/* *********************************************⼆分图匹配（Hopcroft-Carp的算法）。

用匈牙利算法求二分图的最大匹配二分图的最大匹配有两种求法，第一种是最大流；第二种就是匈牙利算法。

这个算法说白了就是最大流的算法，但是它跟据二分图匹配这个问题的特点，把最大流算法做了简化，提高了效率。

最大流算法的核心问题就是找增广路径（augment path）。

匈牙利算法也不例外，它的基本模式就是：初始时最大匹配M为空while 找得到增广路径do 把增广路径加入到最大匹配中去可见和最大流算法是一样的。

但是这里的增广路径就有它一定的特殊性，下面我来分析一下。

（注：匈牙利算法虽然根本上是最大流算法，但是它不需要建网络模型，所以图中不再需要源点和汇点，仅仅是一个二分图。

每条边也不需要有方向。

）图1是我给出的二分图中的一个匹配：［1，5］和［2，6］。

图2就是在这个匹配的基础上找到的一条增广路径：3->6->2->5->1->4。

我们借由它来描述一下二分图中的增广路径的性质：(1)有奇数条边。

(2)起点在二分图的左半边，终点在右半边。

(3)路径上的点一定是一个在左半边，一个在右半边，交替出现。

（其实二分图的性质就决定了这一点，因为二分图同一边的点之间没有边相连。

）(4)整条路径上没有重复的点。

(5)起点和终点都是目前还没有配对的点，而其它所有点都是已经配好对的。

（如图1、图2所示，［1，5］和［2，6］在图1中是两对已经配好对的点；而起点3和终点4目前还没有与其它点配对。

）(6)路径上的所有第奇数条边都不在原匹配中，所有第偶数条边都出现在原匹配中。

（如图1、图2所示，原有的匹配是［1，5］和［2，6］，这两条配匹的边在图2给出的增广路径中分边是第2和第4条边。

而增广路径的第1、3、5条边都没有出现在图1给出的匹配中。

）(7)最重要的一条，把增广路径上的所有第奇数条边加入到原匹配中去，并把增广路径中的所有第偶数条边从原匹配中删除（这个操作称为增广路径的取反），则新的匹配数就比原匹配数增加了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;}下面是从网上的博客摘抄的一些零散的总结。

匈牙利规则
"匈牙利规则"通常指的是在图论中解决二分图匹配问题的一个算法，也称为匈牙利算法或Kőnig算法。

这个算法由匈牙利数学家Dénes Kőnig在1925年提出，用于寻找二分图中的最大匹配。

二分图是一种特殊的图，其顶点可以分成两个不相交的集合，并且图中的每条边都连接这两个集合中的一个顶点。

匈牙利算法的步骤如下：
1. 选择一个未匹配的顶点u from U，U是图中的一半顶点集合。

2. 对于u的每个邻接顶点v from V，如果v尚未匹配，则将其标记为未使用的。

3. 如果u的所有邻接顶点都已被使用，则算法结束，当前匹配是最大匹配。

4. 如果存在一个未使用的顶点v，则将v与u匹配，并转步骤1。

5. 如果u的所有邻接顶点都已被使用，但不是都与u匹配，选择一个与u匹配的顶点w，并找出通过u和w形成的未使用的环。

在这个环上，交替取消匹配的边，直到找到一个未匹配的顶点x。

6. 选择x的一个未使用的邻接顶点y，并取消u与y的匹配。

7. 匹配x和y，并转步骤1。

这个算法可以找到二分图中最大的匹配，并且在实现上相对高效。

它在理论计算机科学和组合优化中有着广泛的应用，例如在网络流问题、调度问题以及一些经济和生物信息学问题中。

一、用匈牙利算法求二分图(二部图,偶图的最大匹配算法中的几个术语说明:1。

二部图:如果图G=(V,E的顶点集何V可分为两个集合X,Y,且满足X∪Y =V, X∩Y=Φ,则G称为二部图;图G的边集用E(G表示,点集用V(G表示。

2。

匹配:设M是E(G的一个子集,如果M中任意两条边在G中均不邻接,则称M是G的一个匹配。

M中的—条边的两个端点叫做在M是配对的。

3。

饱和与非饱和:若匹配M的某条边与顶点v关联,则称M饱和顶点v,并且称v是M-饱和的,否则称v是M-不饱和的。

4。

交互道:若M是二分图G=(V,E的一个匹配。

设从图G中的一个顶点到另一个顶点存在一条道路,这条道路是由属于M的边和不属于M的边交替出现组成的,则称这条道路为交互道。

5。

可增广路:若一交互道的两端点为关于M非饱和顶点时,则称这条交互路是可增广路。

显然,一条边的两端点非饱和,则这条边也是可增广路。

6。

最大匹配:如果M是一匹配,而不存在其它匹配M',使得|M'|>|M|,则称M是最大匹配。

其中|M|表示匹配M的边数。

7。

对称差:A,B是两个集合,定义A⊕B = (A∪B\(A∩B ,则称A⊕B为A和B的对称差。

定理:M为G的最大匹配的充要条件是G中不存在可增广道路。

Hall定理:对于二部图G,存在一个匹配M,使得X的所有顶点关于M饱和的充要条件是:对于X的任意一个子集A,和A邻接的点集为T(A,恒有:|T(A| >= |A|。

匈牙利算法是基于Hall定理中充分性证明的思想,其基本步骤为:1。

任给初始匹配M;2。

若X已饱和则结束,否则进行第3步;3。

在X中找到一个非饱和顶点x0,作V1 ←{x0},V2 ←Φ ;4。

若T(V1 = V2则因为无法匹配而停止,否则任选一点y∈T(V1\V2;5。

若y已饱和则转6,否则做一条从x0→y的可增广路P,M←M⊕E(P,转2;6。

由于y已饱和,所以M中有一条边(y,z,作V1 ←V1∪{z}, V2←V2∪{y},转4;二、用匈牙利算法求二分图的最大匹配(伪代码给定一个二分图(x,y,x中的点和y中点的连接情况,一个匹配是二分图的子图,其中任一个x中的点只能和最多一个y中的点连接,一个y中的点也只能和一个x中的点连接,最大匹配就是使子图中的边数(我们称为匹配边最多的匹配。

匈牙利算法数学模型
匈牙利算法是解决二分图最大匹配问题的一种算法，其数学模型如下：
假设有一个二分图G=(X, Y, E)，其中X和Y分别表示左部顶点集和右部顶点集，E表示二者之间的边集。

对于一个匹配M而言，其由E中的边组成，使得M中的任何两条边都不共享任何顶点。

我们的目标是找到一个最大的匹配，使得匹配的边数最多。

具体实现过程中，可采用以下步骤：
1. 初始化一个最大匹配为空集M；
2. 对于每个左部顶点x，找到其能够匹配的右部顶点集合N(x)；
3. 找到一个未被匹配的左部顶点x，在其能够匹配的右部顶点集合
N(x)中找到一个未被匹配的顶点y；
4. 如果y已经被匹配，将其所在的匹配边(u, y)加入到M中，同时将(x, y)加入到M中，使得u与x之间没有匹配边；
5. 如果y未被匹配，将(x, y)加入到M中，结束。

通过反复执行步骤三到五，直到所有的左部顶点都被匹配。

这样，M就是一个最大的匹配。

但是，匈牙利算法的时间复杂度较高，通常会采用优化方法来提高算法效率。

⼆分图匹配算法（最⼤流匈⽛利）⼆分图匹配相关概念⽆向⼆分图G(U⋃V,E)：U是⼀个顶点集合，V是另⼀个顶点集合，对于⼀个集合内的点⽆边直接相连，⽽对于不同集合的点可以连边，即(u,v)∈E。

匹配：两两不含公共端点的边的集合M称为匹配（就是两个集合之间连的边，只不过不同边的端点不能重合）最⼤匹配：元素最多的M，即⽽G中两两不含公共端点的边的集合M⊆E的基数|M|的最⼤值就是最⼤匹配。

完美匹配：当最⼤匹配的匹配数满⾜2∗|M|=V时，称为完美匹配。

形象的解释就是⼀各集合的所有点到另⼀个集合都有互不相同且唯⼀对应的点。

（类似于函数的双射），想象⼀下图增⼴路：设M为⼆分图G已匹配边的集合，若P是图G中⼀条连通两个未匹配顶点的路径（P的起点在X部，终点在Y部，反之亦可），并且属M的边和不属M的边(即已匹配和待匹配的边)在P上交替出现，则称P为相对于M的⼀条增⼴路径。

(就是连了两个还没有配对的顶点的路径，路径有⼀个配对边，⼀个⾮配对边交替组成)更多详细概念解释见匈⽛利部分的参考⽂章最⼤流的⽅法⼆分图的匹配可以看成是⼀种最⼤流问题（这谁想得出来啊）。

具体过程如下：现在有两个点集U和V，之间已经有了写连边，我们需要引⼊⼀个源，⼀个汇，把源跟集合U的所有点有向地连起来，把V的所有点和汇有向地连起来，就构成了⼀个流⽹络。

现在由于⼆分图匹配的限制，⼀个点不能连⾃⼰内部的点（在原来的⼆分图中这关系已经成⽴），不能连两个或多个边。

那么就把每个边的权值赋为⼀。

这样边的流量只有零壹两种，要么有边，要么不连边。

在上⾯跑最⼤流算法即可（具体讲解参见上篇博客）下⾯是代码：代码:#include <iostream>#include <memory.h>#include <vector>#include <queue>#define max_n 10005#define INF 0x3f3f3f3fusing namespace std;//邻接表struct edge{int v;//到达顶点int cap;//最⼤流量int rev;//对应反向边的编号};vector<edge> G[max_n];int level[max_n];//Dinic算法⽤到的层次图int iter[max_n];//当前弧优化void add_edge(int u,int v,int cap){G[u].push_back((edge){v,cap,G[v].size()});//最后⼀个表⽰uv这条边的反向边在G[v]⾥的标号G[v].push_back((edge){u,0,G[u].size()-1});}void bfs(int s)//处理层次图{memset(level,-1,sizeof(level));queue<int> que;level[s] = 0;que.push(s);while(!que.empty()){int v = que.front();que.pop();for(int i = 0;i<G[v].size();i++){edge& e = G[v][i];if(e.cap>0&&level[e.v]<0){level[e.v] = level[v]+1;que.push(v);}}}}int dfs(int v,int t,int f)//Dinic的dfs{if(v==t) return f;for(int& i = iter[v];i<G[v].size();i++){edge& e = G[v][i];if(e.cap>0&&level[e.v]==level[v]+1){int d = dfs(v,t,min(f,e.cap));if(d>0){G[e.v][e.rev].cap+=d;return d;}}}return 0;}int max_flow(int s,int t)//Dinic算法{int flow = 0;for(;;){bfs(s);if(level[t]<0){return flow;}memset(iter,0,sizeof(iter));int f;while(f=dfs(s,t,INF)>0){flow += f;}}}int N,K;//N,K为两个集合的点数bool can[max_n][max_n];//⼆分图中原有的边void solve(){//0~N-1是U中的点//N~N+K-1是V中的点int s = N+K;int t = s+1;for(int i = 0;i<N;i++)//s与U连边{add_edge(s,i,1);}for(int i = 0;i<K;i++)//t与V连边{add_edge(i+N,t,1);}for(int i = 0;i<N;i++){for(int j = 0;j<K;j++){if(can[i][j]){add_edge(i,j,1);//⼆分图原有边的链接}}}cout << max_flow(s,t) << endl;//求最⼤流即得最⼤匹配}int main(){cin >> N >> K;solve();return 0;}匈⽛利算法这个算法是专门处理⼆分图的最⼤匹配问题的，有很好的博客讲解，下⾯是推荐阅读⽅式：我上⾯的概念可能不太全，那就先来看看⼆分图的相关概念：可能还对增⼴路径不是很理解，什么是增⼴路，⾮配对配对交替什么的很混乱，那不妨先看看这个：现在到了算法流程了，在正式介绍前，先有个有趣⽽深刻的认识，下⾯是⼗分清晰的讲解：好了，该正式⼀点了，相信你也有了⼀定的了解：上⾯的代码其实已经够清晰了，如果还想看⼀下，就这篇吧：代码：#include <iostream>#include <memory.h>#define max_n 200005using namespace std;int n,m;int con_y[max_n];int visit[max_n];int head[max_n];struct edge{int v;int nxt;}e[max_n<<1];int cnt = 0;void add(int u,int v){++cnt;e[cnt].v = v;e[cnt].nxt = head[u];head[u] = cnt;}int dfs(int u){for(int i = head[u];i;i=e[i].nxt){int v = e[i].v;if(visit[v]==0){if(con_y[v]==-1||dfs(v))//结合上⾯算法流程部分的有趣博客再理解了⼀下这⾥的递归，好奇妙 {con_x[u] = v;con_y[v] = u;return 1;}}}return 0;}int Hungary(){memset(con_x,-1,sizeof(con_x));memset(con_y,-1,sizeof(con_y));int ans = 0;for(int i = 1;i<=n;i++){memset(visit,0,sizeof(visit));ans += dfs(i);}return ans;}int main(){cin >> n >> m;for(int i = 1;i<=m;i++){int a,b,c;cin >> a >> b;add(a,b);}cout << Hungary() << endl;return 0;}参考⽂章以上Processing math: 100%。

分布式匈牙利算法分布式匈牙利算法是一种用于解决二分图最大匹配问题的算法。

它将经典匈牙利算法中的搜索过程并行化，从而加快了解决问题的速度。

本文将介绍分布式匈牙利算法的原理、步骤以及应用。

1. 原理分布式匈牙利算法的原理是将一个大的二分图分成若干个小的二分图，每个小二分图可以在一个处理单元上运行，处理单元之间通过通信协作实现匹配过程。

具体来说，算法会将一个大的二分图分为若干个互不相交的子二分图，在每个子二分图中使用经典的匈牙利算法来寻找匹配，然后将匹配好的节点发送给其他的子二分图进行进一步的匹配，直到所有的子二分图都没有匹配可做为止。

分布式匈牙利算法的核心在于如何将大的二分图分解成小的二分图。

这个问题可以通过图分割算法来解决。

常用的图分割算法有最小割算法和谱聚类算法。

最小割算法将图划分为两个互不相交的子图，谱聚类算法则是一种基于矩阵特征值分解的算法，它可以将图划分为若干个互不相交的子图。

2. 步骤步骤1：将大的二分图分解成若干个互不相交的子二分图。

可以使用最小割算法或谱聚类算法实现。

步骤2：在每个子二分图上使用经典的匈牙利算法寻找匹配。

步骤3：将匹配好的节点发送给其他的子二分图进行进一步的匹配。

步骤4：重复步骤2和步骤3，直到所有的子二分图都没有匹配可做为止。

步骤5：将所有子二分图上匹配的结果合并成一个大的匹配结果。

3. 应用分布式匈牙利算法可以应用于解决大型二分图匹配问题。

在实际生产中，分布式匈牙利算法可以应用于图像识别、推荐系统、社交网络等方面。

例如，在推荐系统中，分布式匈牙利算法可以通过将用户和推荐物品分为若干个子二分图，然后在每个子二分图上使用匈牙利算法来寻找匹配，最终得出所有用户和物品的匹配结果。