二分图最大匹配问题(匈牙利算法)

二分图

 二分图是这样的一个图：其顶点可以划分为两个集合 $ X $ 和 $ Y $, 任何一条边所关联的两个顶点中，恰好有一个属于集合 $X$ , 另一个属于 $Y$。 同一个集合内的顶点必没有边相连。如果一个图是二分图，那么它一定没有 奇环 (边为奇数的环路)， 如果一个图没有 奇环 ,那么它就一定是 二分图。

二分图的匹配

 给定一个二分图 G , 在 G 的一个子图 M 中， M 的边集 { E } 中的任意两条边都不依附于同一个顶点， 则称 M 是一个匹配。 翻译成人话就是 在图 G 中找到一些边构成一个集合， 这个集合中的任意一条边所连接的两个顶点都只属于这条边的连个端点，即每条边的顶点都不与其他边共用。如下图： 边集合 E = {(1,5),(3,6),(4,7)} 构成了一个匹配。

最大匹配

 顾名思义，就是最大化满足上述规定的边集 E 。如上图的一个最大匹配结果为：

---

匈牙利算法

 此算法由美国数学家 哈罗德·库恩 于1955年提出该算法。先介绍两个概念：
 交替路： 从一个未匹配顶点出发，依次经过非匹配边、匹配边、非匹配边 … 形成的路径叫作 交替路。
 增广路： 从一个未匹配点出发，走交替路，如果途径另一个未匹配点（出发的点不算），则这条交替路就称为增广路(agumenting path)，且增广路中非匹配边的数目要大于匹配边的数目。 如下图：图中已匹配点带蓝色标记，红色箭头边为一条匹配边，黑色箭头边为非匹配边。

 展开来就是这样的一条 增广路：

 如果此时将上述增广路的 匹配边与非匹配边对调 ：

 不难发现，匹配边多了一条（两条变三条），并且新增了两个匹配顶点。如此一来，边集 E 内不就多了一条边吗，符合我们的目标（最大化边集 E）。因此，匈牙利算法的 核心 就是 不断地寻找增广路径 ，以便可以不断扩大边集 E，得到一个更大的匹配。

总结增广路的定义：

• 其路径长度必定为奇数，且第一条边与最后一条边必定都不属于 M（最大匹配子图）。
• 该路径经过取反操作（匹配变不匹配，不匹配变匹配）后可以得到一个更大的匹配 M’。
• M 为 G 的最大匹配当且仅当不存在相对于 M 的增广路径。

---

算法概述：

1. 从 X 集合中选一个未匹配点 u 作为起点。选一条非匹配边(u,v), 到 Y中的点 v。
2. 如果 v 是为匹配点， 说明找到了一条增广路。
3. 否则若 v 是匹配点，下一步走匹配边，v 恰好和一条匹配边邻接。 设另一端为 left[v], 可以理解为 u 直接走到了 left[v], 也是 X 中的点。
   • 如果始终没有找到未匹配点（找不到最后一条非匹配边）,最后会扩展出一棵匈牙利树（root 是未匹配点， 叶子节点都是匹配点），从 root 到 leaf 的路径都不是增广路。
4. 每次选择一个未匹配点 u 进行 DFS。 如果找不到以 u 开头的增广路，就换一个未匹配点来进行 DFS， 且以后再也不从 u 出发找增广路了。
   • 如果以后存在一个从 u 出发的增广路，那么现在肯定找得到。

---

算法实现：

#include <bits/stdc++.h>
using namespace std;
#define maxn 0x00ff

class BPM { 							 // 二分图的最大奇数匹配
public:
	int n, m, e;						 // 左右顶点个数, 边数
	vector<vector<bool>> G;	     		 // G[x][y] == 1,表示存在边 x - y
	int *left; 				  			 // left[i] 为右边（Y 集合）第i个顶点的匹配顶点编号
	bool *T;						 	 // T[i] = true 表示第i个顶点已经被标记已访问

	BPM() 
	{
		cin >> n >> m >> e;
		T = new bool[maxn];
		left = new int[maxn];
		G = vector<vector<bool>>(maxn,vector<bool>(maxn,false));
		for(int i = 0; i < e; i++)
		{
			int t1, t2;
			cin >> t1 >> t2;
			G[t1][t2] = true;
		}
		memset(T, false, sizeof(T));
		memset(left, -1, sizeof(left));
	}

	bool match(int u)					 // 匈牙利算法
	{
		for(int v = 0; v < m ; v++)		 // 遍历右边 Y 集合中的顶点
		{
			if(G[u][v] && !T[v])
			{
				T[v] = true;
				if(left[v] == -1 || match(left[v]))	// left[v] != -1, left[v] 是 v 的匹配边
				{
					// 若 v 未匹配就将它与 u 匹配(相当于找到了一条增广路 u -> v)，否则通过 v 的匹配点继续找未匹配点
					left[v] = u;
					return true;
				}
			}
		}
		return false;
	}

	int solve() 							// 求最大匹配
	{
		int ans = 0;			            // 匹配数
		for(int u = 0; u < n; u++) 			// 遍历左边顶点寻找增广路
		{
			memset(T, false, sizeof(T));
			if(match(u))
			{
				cout << "--" << endl; 
				ans++; 			// 找到一条增广路
			}
		}
		return ans;
	}
};