二分图是这样的一个图:其顶点可以划分为两个集合 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,得到一个更大的匹配。
总结增广路的定义:
#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;
}
};