匈牙利算法的核心逻辑是不断寻找并翻转增广路：从左部未匹配点出发，沿非匹配边/匹配边交替路径到达右部未匹配点，路径长度为奇数，翻转后匹配数+1；DFS实现中需为每次dfs(u)单独维护vis数组，避免重复访问且保证复杂度为O(nm)。
匈牙利算法的核心逻辑是什么
它不是暴力枚举所有匹配，而是通过不断「找增广路」来扩大当前匹配。每次找到一条从左部未匹配点出发、交替经过非匹配边/匹配边、终点是右部未匹配点的路径，就把这条路径上所有边的状态翻转（匹配变非匹配，非匹配变匹配），匹配数就+1。
关键在于：增广路一定以未匹配点开始和结束，且长度为奇数；翻转后，匹配数严格增加1，且仍保持匹配合法性。
DFS实现匈牙利算法时怎么写递归函数
典型函数签名是 bool dfs(int u)，其中 u 是左部点编号（比如 0~n-1）。函数返回是否能为 u 找到匹配点。
常见错误是忘记在进入递归前标记访问状态，导致死循环或重复尝试同一右部点：
立即学习“C++免费学习笔记（深入）”；
bool dfs(int u) {
for (int v : graph[u]) {
if (vis[v]) continue;
vis[v] = true; // 必须在这！不是在for外统一memset
if (matchR[v] == -1 || dfs(matchR[v])) {
matchR[v] = u;
matchL[u] = v;
return true;
}
}
return false;
}
-
matchL[u]表示左部点u匹配的右部点，初始全为 -1 -
matchR[v]表示右部点v匹配的左部点，初始全为 -1 -
vis[]数组每次调用dfs(u)前要重置为 false（不能全局 memset，否则 O(n²)） - 图用邻接表
vector<vector<int>> graph存，graph[u]存所有与u相邻的右部点索引
为什么每次调用 dfs 都要重置 vis 数组
因为一次 dfs(u) 尝试为 u 找增广路，过程中访问过的右部点 v 如果失败，说明在当前匹配状态下，这些 v 已无法帮 u 构成增广路——再试没意义。但下一轮 dfs(u') 是独立问题，需要重新探索所有 v。
如果复用 vis 或全局清零，会漏掉本可成功的路径；如果每次 memset(vis, 0, sizeof vis)，复杂度退化为 O(nm)，而正确做法是只对本次 DFS 涉及的右部点做局部标记（用 vector
实际跑匈牙利要注意哪些边界和性能坑
左部点数 n、右部点数 m 不一定相等，建图时右部点索引必须从 0 开始连续编号（否则 matchR[v] 数组越界）。
- 图稀疏时（边数
- 如果输入给的是 1-indexed 的点编号，务必先减 1 再存入
graph[u] - 最大匹配数就是最终
matchL中非 -1 的个数，也可用计数器在每次dfs(u)返回 true 时累加 - 最坏时间复杂度 O(nm)，但实际远快于理论值；若超时，优先检查是否误写了
while (dfs(u))这类死循环，或vis未及时重置
增广路本质是“借位调整”，真正难的不是代码，而是理解为什么每次翻转都能净增一个匹配——这点一旦卡住，DFS 的 return 逻辑就容易写反。
