Hungarian algorithm匈牙利算法

主要用来解决不带权的分配问题，O(V*E)

首先，需要明白二分图（又名二部图）的概念

二分图Bipartite Graph

二分图是图论中一种特殊模型。设G=(V,E)是一个无向图(当且仅当图中不存在长度为奇数的环。)，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。

注意：如果一图是二分图，那么它一定没有奇环。如果一图没有奇环的话，那么它可以是二分图。(没有奇环是二分图的必要条件)

▲通常被用来解决分配、匹配问题，如资源分配、工作安排、任务调度……任务的核心本质是求配对关系，或者给顶点和边赋权，求某种条件下的最优分配问题。

△匹配问题可以用网络流解决，或者KM算法（KM算法是一种计算机算法，功能是求完备匹配下的最大权匹配），但是增广路算法更加简洁。

二分图的判定：

染色法1：假设DFS初始点A涂黑色，与它相邻的点就涂白色。如果搜到某一个点u的相邻点v已经涂色并且与u同色，就不可能是二分图啦~

染色法2：就是给每个点进行标号，标为-1，1如果存在一条边连接的两个点标号相同，那么就是存在一个奇数环…

二分图的匹配

匹配：将E的子集M称作一个匹配(子集M中的任意两条边都没有公共端点)
最大匹配：边数最多的匹配称作最大匹配——maximal matching
X(Y)完全匹配：如果X（Y）中的所有的顶点都出现在匹配M中，则称M是X(Y)完全匹配——perfect matching
M完全匹配：如果M既是X-完全匹配，又是Y-完全匹配，称M是完全匹配。此时 $|X| = |Y|$ ，也就是说这个匹配里的所有边刚好经过所有点一次。

最大匹配和完全匹配的应用：

Q：教师-课程安排，G=<U,E,V>，U为教师集合，V为课程集合，E中的边<u,v>表示某位教师u可以上课程v。需要求最大匹配，使得每门课程有人教，每人都有课上。

A:匈牙利算法

匈牙利算法

执行过程

①任意取一个匹配M（可以是空集或只有一条边）
②令S是非饱和点（尚未匹配的点）的集合自如果S=0，则M已经是最大匹配
④从S中取出一个非饱和点山作为起点，从此起点走交错路（交替属于M和非M的边构成的极大无重复点通路或回路）P
③如果P是一个增广路（P的终点也是非饱和点），则令M=MeP=（M-P）U（P-M）
⑥如果P都不是增广路，则从S中去掉uo，转到step3

▲.顶点数不同，即 $|X| \neq |Y|$ 的二分图一定没有完全匹配

▲正则的 $|X| \neq |Y|$ 的二分图一定有完全匹配(正则:每个顶点的度数都相同)

核心思想：不断挪

増广路定理：

任意一个非最大匹配的匹配一定存在增广路。

从一个未匹配点（未盖点）出发，依次经过非匹配边、匹配边、非匹配边…形成的路径叫交替路。
两个端点都是未盖点→增广路（Augmenting Path，AP）
- 比如：8→4→7→1→5→2，图中红色是匹配边。
- 特殊的：3-6也是增广路。
把AP上的匹配边和非匹配边互换，得到的匹配比刚才多一条边。
匹配点只连一条匹配边（？），这样做不会破坏匹配的性质。
增广路定理：即一个匹配是最大匹配等价于不存在增广路。
- 匈牙利算法的核心原理：就是不断找増广路（依据性质3），直至无法找到新的増广路，即为最大匹配。——使用递归（一直找增广路，不断交换匹配）
增广路可以用来改进匹配，最大匹配可以通过反复找增广路来求解。
已经匹配的点永远不会退出匹配，只会更换匹配

注：（匹配点又叫做盖点，非匹配点叫做未盖点（所谓“盖”指的是被一条边盖住）

増广路

实现的细节：

zgl2

每次选一个未盖点u进行DFS。如果找不到u开头的增广路，则换一个未盖点进行DFS，且以后再也不从u出发找增广路。

struct BPM{			//二分图最大基数匹配，邻接矩阵写法
    int n，m，G[maxn][maxn];//左右顶点个数，G[x][y]=1，边x-y
    int left[maxn];		//1eft[i]为右边第i个点的匹配点编号，-1表示不存在
    bool T[maxn];		//T[i]为右边第i个点是否已标记
    void init(int n，int m){
    this->n=n，this->m=m;_zero(G);
}
    
bool match(int u){		// 递归进行挪
	for(intv=e;v<m;v++)
        if(G[u][v]&&！T[v]){
            T[v]=true;
            if(left[v]==-1 || match(left[v])){
            //left[v]！=-1，1eft[v]-v是匹配边
            left[v]=u;
            return true;
		}
	}
    return false;
}
    
int solve（){ //求最大匹配
    memset(left，-1，sizeof(left));
    int ans=0;
    for(int u=e;u<n;u++){//从左边结点u开始增广
        _zero(T); 
        if(match(u)) ans++;//u是未盖点
    }
    return ans;
	}
};

具体实现代码见文章：《ACM-二分图》

其他相关概念：

最小顶点覆盖：

是指最少的顶点数使得二分图G中的每条边都至少与其中一个点相连
&二分图的最小顶点覆盖数=二分图的最大匹配数

DAG最小不相交路径覆盖

也称为最小边覆盖，是指用尽量少的顶点不相交（只经过一次）的简单路径覆盖二分图中的所有顶点
路径长度可以为0
&二分图的最小路径覆盖数=|V|-二分图的最大匹配数
*最小可相交路径覆盖

最大独立集

最大独立集是指寻找一个点集，使得其中任意两点在图中无对应边。
对于一般图来说，最大独立集是一个NP完全问题，对于二分图来说最大独立集
=|V| - 二分图的最大匹配数

KM(Kuhn-Munkres)算法

带权二分图最佳完美匹配，O(n^3)，（运用匈牙利算法辅助求解）

只适用于带权最大匹配一定是完备匹配的情况，实践中建议用费用流来解决。
完全二分图一定是偶数个点
可行顶标（Feasible Labeling）：结点函数（x），任意边（x，y）：1（x）+l（y）≥w（xiy）。
相等子图：G的生成子图，包含所有点以及满足l（x）+I（y）=w（x，y）的边（x，y）
如果EL有完美匹配为PM，则该M是原图的最大权匹配：
- PM的权和等于所有点的顶标之和SV。
- G的任一个最大权匹配M，边满足w（xy）≤l（x）+（y）→M边权和≤SV=PM边权和
- 关键就是寻找好的可行顶标，使相等子图有完美匹配。

==>找到原图的完美匹配–只要–>找到相等子图的完美匹配即可

▲KM完成之后所有的l(x)之和最小

举个栗子:

少林决胜(Golden Tiger Claw，UVa11383)

给定一个N*N矩阵，每个格子里都有一个正整数w(i,j)。你的任务是给每行确定一个整数row(i)，每列也确定一个整数col(i)，使得对于任意格子(i, j)，w(i, j)≤row(i)+colj)。所有row(i)和col(i)之和应尽量小。

【分析】
1.行看作二分图X点，列看作二分图Y点。
2.和最佳匹配没有任何关系，KM算法副产品。
3.KM中算法等式l（x）+l（y）≥w（x，y）。行X，列Y。
4.KM过程中，所有顶标不断减小，算法结束后，所有顶标之和是最小的。

蚂蚁（Ants，NEERC2008，LA4043）

给出n个白点和n个黑点的坐标，要求用n条不相交的线段把它们连接起来，其中每条线段恰好连接一个白点和一个黑点，每个点恰好连接到一条线段，如图所示。

【分析】

点有黑白两色，构造二分图，白X黑Y。每个黑点和每个白点相连，权值等于欧氏距离。
连接方案实际上是计算一个完美匹配，匹配中假设al-b1与a2-b2相交，那么dist(a1，b1)+dist(a2，b2)>dist(al，b2)+dist(a2，b1)，这两条线段改成al-b2和a2-b1后总长度会变少。
所以最小匹配中不会出现线段相交。
套KM算法即可计算最小完美匹配即可。

参考资料：

离散数学：图论：二分图的匹配——陈斌北京大学地球与空间科学学院

二分匹配——匈牙利算法和KM算法——里面推荐的文章更值得一看

带你入门多目标跟踪（三）匈牙利算法&KM算法——以图像目标跟踪距离

二分图匹配问题与匈牙利算法——里面包含概念挺全的

二分图大合集——二分图最大匹配（最小覆盖数），完美匹配以及最优匹配（带权最大匹配）——对概念的介绍比上个更准确点，推荐

二分图最大匹配以及常见模型——ACM角度

任务分配问题—匈牙利算法——含Gungary算法执行过程伪代码