二分图匹配与匈牙利算法详解

1. 二分图匹配问题概述

二分图匹配是图论中的一个经典问题，也是信息学竞赛中的常见考点。简单来说，二分图是指顶点可以划分为两个不相交集合的图，使得每条边的两个端点分别属于这两个集合。匹配则是指一组没有公共顶点的边。

在实际应用中，二分图匹配可以用来解决许多资源分配问题。比如：

• 学生与导师的双向选择
• 求职者与岗位的匹配
• 医院与实习医生的分配

在信奥竞赛中，B3605这道题考察的就是如何用算法高效地找到二分图中的最大匹配。理解这个问题的解法，不仅能帮助我们应对竞赛，也能培养解决实际问题的思维能力。

2. 问题建模与输入输出分析

2.1 题目输入格式解析

典型的二分图匹配题目输入通常包含以下信息：

1. 二分图两个部分的顶点数量（n和m）
2. 图中的总边数（e）
3. 每条边的具体连接关系（u连接v）

例如输入可能是：

code复制4 4 6
1 1
1 2
2 2
2 3
3 1
4 3

这表示左边有4个顶点，右边有4个顶点，共6条边。

2.2 输出要求理解

题目通常要求输出：

1. 最大匹配数
2. 具体的匹配方案（每条匹配边）

对于上面的示例，正确输出应该是：

code复制3
1 2
2 3
3 1

3. 匈牙利算法详解

3.1 算法核心思想

匈牙利算法是解决二分图匹配问题的经典方法，其核心是：

1. 从左边未匹配顶点开始
2. 寻找增广路径（交替经过匹配边和非匹配边的路径）
3. 如果找到增广路径，则反转路径上的边状态（匹配变非匹配，非匹配变匹配）

这个算法之所以有效，是因为每次找到增广路径都能使匹配数增加1。

3.2 C++实现步骤

以下是匈牙利算法的标准实现框架：

cpp复制#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

const int MAXN = 1005;
vector<int> G[MAXN];  // 邻接表存图
int match[MAXN];      // 记录匹配关系
bool vis[MAXN];       // 访问标记

bool dfs(int u) {
    for(int v : G[u]) {