转载自：https://blog.csdn.net/thunderMrbird/article/details/52231639
二分图：简单来说，如果图中点可以被分为两组，并且使得所有边都跨越组的边界，则这就是一个二分图。准确地说：把一个图的顶点划分为两个不相交集 U 和 V ，使得每一条边都分别连接 U、V 中的顶点。如果存在这样的划分，则此图为一个二分图。二分图的一个等价定义是：不含有「含奇数条边的环」的图。图 1 是一个二分图。为了清晰，我们以后都把它画成图 2 的形式。
匹配：在图论中，一个「匹配」（matching）是一个边的集合，其中任意两条边都没有公共顶点。例如，图 3、图 4 中红色的边就是图 2 的匹配。
我们定义匹配点、匹配边、未匹配点、非匹配边，它们的含义非常显然。例如图 3 中 1、4、5、7 为匹配点，其他顶点为未匹配点；1-5、4-7为匹配边，其他边为非匹配边。
最大匹配：一个图所有匹配中，所含匹配边数最多的匹配，称为这个图的最大匹配。图 4 是一个最大匹配，它包含 4 条匹配边。
完美匹配：如果一个图的某个匹配中，所有的顶点都是匹配点，那么它就是一个完美匹配。图 4 是一个完美匹配。显然，完美匹配一定是最大匹配（完美匹配的任何一个点都已经匹配，添加一条新的匹配边一定会与已有的匹配边冲突）。但并非每个图都存在完美匹配。
举例来说：如下图所示，如果在某一对男孩和女孩之间存在相连的边，就意味着他们彼此喜欢。是否可能让所有男孩和女孩两两配对，使得每对儿都互相喜欢呢？图论中，这就是完美匹配问题。如果换一个说法：最多有多少互相喜欢的男孩/女孩可以配对儿？这就是最大匹配问题。
基本概念讲完了。求解最大匹配问题的一个算法是匈牙利算法，下面讲的概念都为这个算法服务。
交替路：从一个未匹配点出发，依次经过非匹配边、匹配边、非匹配边…形成的路径叫交替路。
增广路：从一个未匹配点出发，走交替路，如果途径另一个未匹配点（出发的点不算），则这条交替路称为增广路（agumenting path）。例如，图 5 中的一条增广路如图 6 所示（图中的匹配点均用红色标出）：
增广路有一个重要特点：非匹配边比匹配边多一条。因此，研究增广路的意义是改进匹配。只要把增广路中的匹配边和非匹配边的身份交换即可。由于中间的匹配节点不存在其他相连的匹配边，所以这样做不会破坏匹配的性质。交换后，图中的匹配边数目比原来多了 1 条。
我们可以通过不停地找增广路来增加匹配中的匹配边和匹配点。找不到增广路时，达到最大匹配（这是增广路定理）。匈牙利算法正是这么做的。在给出匈牙利算法 DFS 和 BFS 版本的代码之前，先讲一下匈牙利树。
匈牙利树一般由 BFS 构造（类似于 BFS 树）。从一个未匹配点出发运行 BFS（唯一的限制是，必须走交替路），直到不能再扩展为止。例如，由图 7，可以得到如图 8 的一棵 BFS 树：
这棵树存在一个叶子节点为非匹配点（7 号），但是匈牙利树要求所有叶子节点均为匹配点，因此这不是一棵匈牙利树。如果原图中根本不含 7 号节点，那么从 2 号节点出发就会得到一棵匈牙利树。这种情况如图 9 所示（顺便说一句，图 8 中根节点 2 到非匹配叶子节点 7 显然是一条增广路，沿这条增广路扩充后将得到一个完美匹配）。
-------等等，看得头大？那么请看下面的版本：
通过数代人的努力，你终于赶上了剩男剩女的大潮，假设你是一位光荣的新世纪媒人，在你的手上有N个剩男，M个剩女，每个人都可能对多名异性有好感（
本着救人一命，胜造七级浮屠的原则，你想要尽可能地撮合更多的情侣，匈牙利算法的工作模式会教你这样做：
===============================================================================
一： 先试着给1号男生找妹子，发现第一个和他相连的1号女生还名花无主，got it，连上一条蓝线
===============================================================================
二：接着给2号男生找妹子，发现第一个和他相连的2号女生名花无主，got it
===============================================================================
三：接下来是3号男生，很遗憾1号女生已经有主了，怎么办呢？
我们试着给之前1号女生匹配的男生（也就是1号男生）另外分配一个妹子。
(黄色表示这条边被临时拆掉)
与1号男生相连的第二个女生是2号女生，但是2号女生也有主了，怎么办呢？我们再试着给2号女生的原配(
此时发现2号男生还能找到3号女生，那么之前的问题迎刃而解了，回溯回去
2号男生可以找3号妹子~~~ 1号男生可以找2号妹子了~~~ 3号男生可以找1号妹子
所以第三步最后的结果就是：
===============================================================================
四： 接下来是4号男生，很遗憾，按照第三步的节奏我们没法给4号男生腾出来一个妹子，我们实在是无能为力了……香吉士同学走好。
===============================================================================
hdu2063：
hdu2063就是一道裸二分图最大匹配的问题，直接上匈牙利算法即可。
#include<iostream>
#include<cstring>
#include<cmath>
#include<stdio.h>
#include<algorithm>
#include<iomanip>
using namespace std;
#define N 500+5
int line[N][N], girl[N], vis[N], k, m, n;
bool find(int x) {
for(int i=1;i<=n;i++)//逐个扫描每个男生
if(line[x][i] && !vis[i]) {//line表示两人是否有关系，girl表示该男生的女伴，vis表示该男生是否被询问过
vis[i]=1;
if(girl[i]==0 || find(girl[i])) {//递归回溯
girl[i]=x;
return true;
}
}
return false;
}
int main() {
int x, y;
while(scanf("%d", &k) && k) {
scanf("%d%d", &m, &n);
memset(girl, 0, sizeof(girl));
memset(line, 0, sizeof(line));
for(int i=1;i<=k;i++) {
scanf("%d%d", &x, &y);
line[x][y]=1;//表示女生x和男生y有关系
}
int cnt=0;
for(int i=1;i<=m;i++) { //逐个扫描每个女生，为她们寻找最佳伴侣
memset(vis, 0, sizeof(vis));//每次循环将标志都清零
if(find(i))
cnt++;
}
printf("%d\n", cnt);
}
return 0;
}
二分图最优匹配：
接下来就是二分图最优匹配的km算法了
km算法理解起来着实很困难，我其实只能照着代码讲，不然根本讲不明白。不过听一个学长说要理解思想而不是代码。。。那就试着空讲一下吧。
一般对KM算法的描述，基本上可以概括成以下几个步骤：（1） 初始化可行标杆
（2） 用匈牙利算法寻找完备匹配
（3） 若未找到完备匹配则修改可行标杆
（4） 重复（2）（3）直到找到相等子图的完备匹配
关于该算法的流程及实施，网上有很多介绍，基本上都是围绕可行标杆如何修改而进行的讨论，至于原理并没有给出深入的探讨。
KM算法是用于寻找带权二分图最佳匹配的算法。
二分图是这样一种图：所有顶点可以分成两个集：X和Y，其中X和Y中的任意两个在同一个集中的点都不相连，而来自X集的顶点与来自Y集的顶点有连线。当这些连线被赋于一定的权重时，这样的二分图便是带权二分图。
二分图匹配是指求出一组边，其中的顶点分别在两个集合中，且任意两条边都没有相同的顶点，这组边叫做二分图的匹配，而所能得到的最大的边的个数，叫做二分图的最大匹配。
我们也可以换个角度看二分图的最大匹配，即二分图的每条边的默认权重为1，我们求到的二分图的最大匹配的权重最大。对于带权二分图，其边有大于0的权重，找到一组匹配，使其权重最大，即为带权二分图的最佳匹配。
匈牙利算法一般用于寻找二分图的最大匹配。算法根据一定的规则选择二分图的边加入匹配子图中，其基本模式为：
初始化匹配子图为空
While 找得到增广路径
Do 把增广路径添加到匹配子图中
增广路径有如下特性：
1. 有奇数条边
2. 起点在二分图的X边，终点在二分图的Y边
3. 路径上的点一定是一个在X边，一个在Y边，交错出现。
4. 整条路径上没有重复的点
5. 起点和终点都是目前还没有配对的点，其他的点都已经出现在匹配子图中
6. 路径上的所有第奇数条边都是目前还没有进入目前的匹配子图的边，而所有第偶数条边都已经进入目前的匹配子图。奇数边比偶数边多一条边
7. 于是当我们把所有第奇数条边都加到匹配子图并把条偶数条边都删除，匹配数增加了1.
例如下图，蓝色的是当前的匹配子图，目前只有边x0y0，然后通过x1找到了增广路径：x1y0->y0x0->x0y2
其中第奇数第边x1y0和x0y2不在当前的匹配子图中，而第偶数条边x0y0在匹配子图中，通过添加x1y0和x0y2到匹配子图并删除x0y0，使得匹配数由1增加到了2。每找到一条增广路径，通过添加删除边，我们总是能使匹配数加1.
增广路径有两种寻径方法，一个是深搜，一个是宽搜。例如从x2出发寻找增广路径，如果是深搜，x2找到y0匹配，但发现y0已经被x1匹配了，于是就深入到x1，去为x1找新的匹配节点，结果发现x1没有其他的匹配节点，于是匹配失败，x2接着找y1，发现y1可以匹配，于是就找到了新的增广路径。如果是宽搜，x1找到y0节点的时候，由于不能马上得到一个合法的匹配，于是将它做为候选项放入队列中，并接着找y1，由于y1已经匹配，于是匹配成功返回了。相对来说，深搜要容易理解些，其栈可以由递归过程来维护，而宽搜则需要自己维护一个队列，并对一路过来的路线自己做标记，实现起来比较麻烦。
对于带权重的二分图来说，我们可以把它看成一个所有X集合的顶点到所有Y集合的顶点均有边的二分图（把原来没有的边添加入二分图，权重为0即可），也就是说它必定存在完备匹配（即其匹配数为min(|X|,|Y|)）。为了使权重达到最大，我们实际上是通过贪心算法来选边，形成一个新的二分图（我们下面叫它二分子图好了），并在该二分图的基础上寻找最大匹配，当该最大匹配为完备匹配时，我们可以确定该匹配为最佳匹配。（在这里我们如此定义最大匹配：匹配边数最多的匹配和最佳匹配：匹配边的权重和最大的匹配。）
贪心算法总是将最优的边优先加入二分子图，该最优的边将对当前的匹配子图带来最大的贡献，贡献的衡量是通过标杆来实现的。下面我们将通过一个实例来解释这个过程。
有带权二分图：
算法把权重转换成标杆，X集跟Y集的每个顶点各有一个标杆值，初始情况下权重全部放在X集上。由于每个顶点都将至少会有一个匹配点，贪心算法必然优先选择该顶点上权重最大的边（最理想的情况下，这些边正好没有交点，于是我们自然得到了最佳匹配）。最初的二分子图为：（可以看到初始化时X标杆为该顶点上的最大权重，而Y标杆为0）
从X0找增广路径，找到X0Y4；从X1找不到增广路径，也就是说，必须往二分子图里边添加新的边，使得X1能找到它的匹配，同时使权重总和添加最大。由于X1通往Y4而Y4已经被X0匹配，所以有两种可能，一个是为X0找一个新的匹配点并把Y4让给X1，或者是为X1找一个新的匹配点，现在我们将要看到标杆的作用了。根据传统的算法描述，能够进入二分子图的边的条件为L(x)+L(y)>=weight(xy)。当找不到增广路径时，对于搜索过的路径上的XY点，设该路径上的X顶点集为S，Y顶点集为T，对所有在S中的点xi及不在T中的点yj，计算d=min{(L(xi)+L(yj)-weight(xiyj))}，从S集中的X标杆中减去d，并将其加入到T集中的Y的标杆中，由于S集中的X标杆减少了，而不在T中的Y标杆不变，相当于这两个集合中的L(x)+L(y)变小了，也就是，有新的边可以加入二分子图了。从贪心选边的角度看，我们可以为X0选择新的边而抛弃原先的二分子图中的匹配边，也可以为X1选择新的边而抛弃原先的二分子图中的匹配边，因为我们不能同时选择X0Y4和X1Y4，因为这是一个不合法匹配，这个时候，d=min{(L(xi)+L(yj)-weight(xiyj))}的意义就在于，我们选择一条新的边，这条边将被加入匹配子图中使得匹配合法，选择这条边形成的匹配子图，将比原先的匹配子图加上这条非法边组成的非法匹配子图的权重和（如果它是合法的，它将是最大的）小最少，即权重最大了。好绕口的。用数学的方式表达，设原先的不合法匹配（它的权重最大，因为我们总是从权重最大的边找起的）的权重为W，新的合法匹配为W’，d为min{W-W’i}。在这个例子中，S={X0, X1}，Y={Y4}，求出最小值d=L(X1)+L(Y0)-weight(X1Y0)=2，得到新的二分子图：
重新为X1寻找增广路径，找到X1Y0，可以看到新的匹配子图的权重为9+6=15，比原先的不合法的匹配的权重9+8=17正好少d=2。
接下来从X2出发找不到增广路径，其走过的路径如蓝色的路线所示。形成的非法匹配子图：X0Y4，X1Y0及X2Y0的权重和为22。在这条路径上，只要为S={X0，X1，X2}中的任意一个顶点找到新的匹配，就可以解决这个问题，于是又开始求d。
d=L(X0)+L(Y2)-weight(X0Y2)=L(X2)+L(Y1)-weight(X2Y1)=1.
新的二分子图为：
重新为X2寻找增广路径，如果我们使用的是深搜，会得到路径：X2Y0->Y0X1->X1Y4->Y4X0->X0Y2，即奇数条边而删除偶数条边，新的匹配子图中由这几个顶点得到的新的权重为21；如果使用的是宽搜，会得到路径X2Y1，另上原先的两条匹配边，权重为21。假设我们使用的是宽搜，得到的新的匹配子图为：
接下来依次类推，直到为X4找到一个匹配点。
KM算法的最大特点在于利用标杆和权重来生成一个二分子图，在该二分子图上面找最大匹配，而且，当些仅当找到完备匹配，才能得到最佳匹配。标杆和权重的作用在于限制新边的加入，使得加入的新边总是能为子图添加匹配数，同时又令权重和得到最大的提高。