匈牙利算法核心是增广路搜索而非暴力枚举，通过dfs/bfs寻找从未匹配左部点出发、交替经过非匹配边与匹配边、终点为未匹配右部点的路径，找到即翻转边状态使匹配数+1。
匈牙利算法核心是增广路搜索，不是暴力枚举
很多人一上来就想着“怎么把所有匹配试一遍”，结果写成指数级回溯。匈牙利算法本质是不断找一条从**未匹配左部点出发、交替经过非匹配边/匹配边、终点为未匹配右部点**的路径——也就是增广路。找到就翻转边的状态，匹配数+1。
关键判断逻辑在 dfs 或 bfs 里：对当前左部点 u，遍历所有邻接右部点 v；若 v 未被匹配，或 v 当前匹配的左部点能腾出位置（递归检查），则 u 可以连上 v。
- 必须维护
matchR[v]（右部点v匹配的左部点）和matchL[u]（左部点u匹配的右部点），初始全为 -1 或 0 - 每次尝试新左部点前，要重置
visited标记数组（或用时间戳优化），否则会漏搜 - 邻接表建议用
vector<vector>></vector>存左部点的邻居，别用 map 或 set —— 增广路搜索对遍历顺序不敏感，但常数很重要
DFS 实现比 BFS 更常用，但要注意栈溢出风险
教科书和 OJ 题解大多用 DFS，代码短、逻辑直。但它隐含递归深度 = 左部点数 × 最长增广路长度，在稠密图或点数上千时可能爆栈。
典型错误是没设好递归终止条件，或把 visited 数组放在函数参数里传值复制，导致状态失效。
立即学习“C++免费学习笔记（深入）”；
-
dfs(u)返回 bool，表示左部点u是否成功找到增广路 -
visited[v]必须是全局或引用传递的布尔数组，标记本轮 DFS 中右部点v是否已访问过（防环） - 递归调用前先标
visited[v] = true，失败也不需要“回退”——这不是回溯，是单轮尝试 - 点数 > 5000 且链式结构明显时，改用 BFS（即 Hopcroft-Karp 的简化版）更稳
建图时别混淆左右部点编号，二分图必须物理分离
常见错误：读入边 (a, b) 后直接存 graph[a].push_back(b)，但没确认 a 属于左部、b 属于右部。C++ 不像 Python 有类型提示，编译器不会报错，但匹配结果全乱。
尤其当左右部点编号范围重叠（比如都是 1~n），必须人为隔离：例如左部点用 0~n-1，右部点用 0~m-1，或统一偏移（右部点编号 + n）。
- 输入阶段就明确划分：读入后立刻检查
a是否 ∈ [0, n)、b是否 ∈ [0, m)，否则 assert 或跳过 - 邻接表大小按左部点数
n开：vector<vector>> graph(n)</vector>，每个graph[u]存的是右部点下标 - 匹配数组
matchR长度必须是右部点总数m，越界访问会触发std::out_of_range或静默错误
匈牙利算法只保证最大基数匹配，不处理权重
看到“匹配”就默认要 KM 算法？不是。标准匈牙利算法（Kuhn-Munkres 前身）只解决无权二分图的最大匹配。如果边有权重要最大权匹配，必须换 KM，复杂度从 O(V*E) 升到 O(V²*E)，代码量翻三倍。
线上调试时发现匹配数正确但总权值偏低，第一反应不该是调匈牙利，而是确认问题本身是否带权。
- 检查题目描述：出现 “sum of weights”、“maximum total score”、“cost” 等词 → 必须用 KM
- 匈牙利算法中所有边等价，
graph[u][i]只存右部点索引，不存权值；加权后这个结构就不够了 - 即使强行把权值当存在性（如权 > 0 才连边），也得不到最大权解，只是某个可行匹配
visited 数组的生命周期和初始化时机——它必须每轮外层 for 循环都清零，且不能复用上一轮的残留标记。这点在多组数据或多次调用时特别容易出错。 
