Hungarian_algorithm 匈牙利算法

二分图：简单来说，如果图中点可以被分为两组，并且使得所有边都跨越组的边界，则这就是一个二分图。准确地说：把一个图的顶点划分为两个不相交集 和 ，使得每一条边都分别连接 中的顶点。如果存在这样的划分，则此图为一个二分图。二分图的一个等价定义是：不含有「含奇数条边的环」的图。
最大匹配：一个图所有匹配中，所含匹配边数最多的匹配，称为这个图的最大匹配。
完美匹配：如果一个图的某个匹配中，所有的顶点都是匹配点，那么它就是一个完美匹配。显然，完美匹配一定是最大匹配（完美匹配的任何一个点都已经匹配，添加一条新的匹配边一定会与已有的匹配边冲突）。但并非每个图都存在完美匹配。
交替路：从一个未匹配点出发，依次经过非匹配边、匹配边、非匹配边…形成的路径叫交替

增广路：从一个未匹配点出发，走交替路，如果途径另一个未匹配点（出发的点不算），则这条交替路称为增广路（agumenting path）。
增广路有一个重要特点：非匹配边比匹配边多一条。因此，研究增广路的意义是改进匹配。只要把增广路中的匹配边和非匹配边的身份交换即可。由于中间的匹配节点不存在其他相连的匹配边，所以这样做不会破坏匹配的性质。交换后，图中的匹配边数目比原来多了 1 条。

我们可以通过不停地找增广路来增加匹配中的匹配边和匹配点。找不到增广路时，达到最大匹配（这是增广路定理）。匈牙利算法正是这么做的。在给出匈牙利算法 DFS 和 BFS 版本的代码之前，先讲一下匈牙利树。
匈牙利树一般由 BFS 构造（类似于 BFS 树）。从一个未匹配点出发运行 BFS（唯一的限制是，必须走交替路），直到不能再扩展为止。
// 由于时间紧凑，代码摘自http://dsqiu.iteye.com/blog/1689505
#define maxn 10//表示x集合和y集合中顶点的最大个数！

int nx,ny;//x集合和y集合中顶点的个数

int edge[maxn][maxn];//edge[i][j]为1表示ij可以匹配

int cx[maxn],cy[maxn];//用来记录x集合中匹配的y元素是哪个！

int visited[maxn];//用来记录该顶点是否被访问过！

int path(int u)
{

int v;

for(v=0;v<ny;v++)

{

if(edge[u][v]&&!visited[v])

{

visited[v]=1;

if(cy[v]==-1||path(cy[v]))//如果y集合中的v元素没有匹配或者是v已经匹配，但是从cy[v]中能够找到一条增广路

{

cx[u]=v; //找到增广路，修改匹配M

cy[v]=u;

return 1;

}

}

}

return 0;

}

int maxmatch()

{

int res=0;

memset(cx,0xff,sizeof(cx));//初始值为-1表示两个集合中都没有匹配的元素！

memset(cy,0xff,sizeof(cy));

for(int i=0;i<=nx;i++)

{

if(cx[i]==-1) //还没被匹配，执行内部代码

{

memset(visited,0,sizeof(visitited)); //重置标记为为访问

res+=path(i); //以 i 为起点开始查找增广路，返回true ，匹配数+1

}

}

return res;

}

一、二分图最大匹配
定义：匹配是图中一些边的集合，且集合中任意两条边都没有公共点，所有的匹配中，边数最多的就是最大匹配。
算法：用匈牙利算法可以在O(V*E)的复杂度内求出二分图的最大匹配，具体可以看byvoid神犇的blog，讲的很详细，不过想真正完全证明这个算法，得去看组合数学。

二、二分图最小点覆盖
定义：点覆盖是图中一些点的集合，且对于图中所有的边，至少有一个端点属于点覆盖，点数最小的覆盖就是最小点覆盖。
定理：最小点覆盖=最大匹配。
　　 注：此处证明直接参考二分图中的最大匹配数等于最小点覆盖数的证明
简单证明：首先必然有，最小覆盖>=最大匹配。于是只要证明不等式可以取等号，我们可在最大匹配的基础上构造出一组点覆盖。对右边每一个未匹配的点进行dfs找增广路，标记所有dfs过程中访问到的点，左边标记的点+右边未标记的点就是这个图的一个点覆盖。因为对于任意一条边，如果他的左边没标记，右边被标记了，那么我们就可找到一条新的增广路，所以每一条边都至少被一个点覆盖。再来证明：最大匹配=左边标记的点+右边未标记的点。对于每条匹配边，只有一个点属于点覆盖。如果这条边在dfs过程中被访问了，那么就左端点属于点覆盖，右端点不属于，否则就有左端点不属于点覆盖，右端点属于点覆盖。除此之外，不可能存在其它的点属于最小覆盖了，不然就必然可以找到增广路。所以：左边标记的点+右边未标记的点=最大匹配，对于任意的二分图，我们总能在最大匹配的基础上构造出一组点数等于最大匹配的点覆盖，所以：最小点覆盖=最大匹配。

三、二分图最小边覆盖
定义：边覆盖是图中一些边的集合，且对于图中所有的点，至少有一条集合中的边与其相关联，边数最小的覆盖就是最小边覆盖。
定理：最小边覆盖=图中点的个数-最大匹配。
简单证明：先贪心的选一组最大匹配的边加入集合，对于剩下的每个未匹配的点，随便选一条与之关联的边加入集合，得到的集合就是最小边覆盖，所以有：最小边覆盖=最大匹配+图中点的个数-2*最大匹配=图中点的个数-最大匹配。

四、二分图最大独立集
定义：独立集是图中一些点的集合，且图中任意两点之间都不存在边，点数最大的就是最大独立集。
定理：最大独立集=图中点的个数-最大匹配。
简单证明：可以这样来理解，先把所有的点都加入集合，删除最少的点和与其关联的边使得剩下的点相互之间不存在边，我们就得到了最大独立集。所以有：最大独立集=图中点的个数-最小点覆盖=图中点的个数-最大匹配。

五、有向无环图最小不相交路径覆盖
定义：用最少的不相交路径覆盖所有顶点。
定理：把原图中的每个点V拆成Vx和Vy，如果有一条有向边A->B，那么就加边Ax-By。这样就得到了一个二分图，最小路径覆盖=原图的节点数-新图最大匹配。
简单证明：一开始每个点都独立的为一条路径，总共有n条不相交路径。我们每次在二分图里加一条边就相当于把两条路径合成了一条路径，因为路径之间不能有公共点，所以加的边之间也不能有公共点，这就是匹配的定义。所以有：最小路径覆盖=原图的节点数-新图最大匹配。

六、有向无环图最小可相交路径覆盖
定义：用最小的可相交路径覆盖所有顶点。
算法：先用floyd求出原图的传递闭包，即如果a到b有路，那么就加边a->b。然后就转化成了最小不相交路径覆盖问题。

七、偏序集的最大反链
定义：偏序集中的最大独立集。
Dilworth定理：对于任意偏序集都有，最大独立集（最大反链）=最小链的划分（最小不相交路径覆盖）。
通过Dilworth定理，我们就可以把偏序集的最大独立集问题转化为最小不相交路径覆盖问题了。

八、二分图带权最大匹配
定义：每个边都有一组权值，边权之和最大的匹配就是带权最大匹配。
算法：KM算法，复杂度为O（V^3）。具体就不说了，网上有不少资料。
要注意的是，KM算法求的是最佳匹配，即在匹配是完备的基础上权值之和最大。这和带权最大匹配是不一样的，不过我们可以加入若干条边权为0的边使得KM求出来的最佳匹配等于最大权匹配。具体实现的时候最好用矩阵来存图，因为一般点的个数都是10^2级别，并且这样默认任意两点之间都存在边权为0的边，写起来很方便。如果要求最小权匹配，我们可以用一个很大数减去每条边的边权