木-Star1. 项目概述：二分图匹配在信奥中的核心价值
第一次接触二分图匹配是在省队选拔赛的压轴题上，那道题用匈牙利算法就能轻松解决，但当时我对着题目发了半小时呆。后来系统学习才发现，二分图匹配不仅是图论中的经典问题，更是信奥竞赛中频繁出现的"常客"。
B3605这道题看似简单，却涵盖了图论建模、算法选择和实现优化三大核心能力。题目要求我们在给定的二分图中找到最大匹配数，这在实际竞赛中对应着诸如任务分配、课程安排等常见场景。举个例子，假设有n个学生和m门选修课，每个学生有若干意向课程，如何最大化满足学生选课需求？这就是典型的二分图匹配问题。
需要模型API调用？ 免费领10W Token，多模型网关一键接入 Claude、DeepSeek 等主流模型。
2. 二分图基础与问题建模
2.1 二分图的数学定义与特性
二分图（Bipartite Graph）是指顶点集V可以划分为两个不相交的子集A和B，并且图中每条边都连接着A和B中的顶点。用数学表达式表示就是：
V = A ∪ B, A ∩ B = ∅
∀e = (u,v) ∈ E, u ∈ A ∧ v ∈ B
判断一个图是否是二分图，可以使用染色法：从任意顶点出发，用两种颜色交替染色，如果出现相邻顶点同色则不是二分图。这个特性在竞赛中经常作为前置判断题出现。
2.2 题目B3605的具体建模方法
题目通常会给出两部分顶点及其连接关系。例如输入格式可能是：
n m e // A部点数|B部点数|边数
e行(u,v) // 表示A部的u与B部的v相连
在实际编码中，我们常用邻接表存储这种结构：
cpp复制vector<int> adj[MAXN]; // MAXN根据题目规模设定
void addEdge(int u, int v) {
adj[u].push_back(v);
}
重要提示：竞赛中务必注意顶点编号起始位置！有些题目从1开始，而算法实现通常需要从0开始，需要进行转换。
3. 匈牙利算法深度解析
3.1 算法核心思想与执行流程
匈牙利算法就像一场精心安排的相亲大会：A组的每个成员轮流尝试与B组匹配，如果心仪对象已有人选，就请对方看看能否换一个伴侣。用专业术语说就是"寻找增广路径"。
算法步骤：
- 初始化所有顶点未匹配
- 对A部每个顶点u执行DFS/BFS：
- 标记u已访问
- 对u的每个邻接点v：
- 如果