C++怎么实现匈牙利算法_C++二分图最大匹配【匹配】

匈牙利算法核心是dfs/bfs找增广路以增广匹配，需正确初始化match[]为-1、每轮重置used[]，通过递归尝试腾位更新match[y]=x；邻接表优于邻接矩阵，注意边方向与下标统一。

匈牙利算法的核心是“找增广路”，不是暴力枚举

直接写个双重循环试图穷举所有匹配，会超时或错解。匈牙利算法本质是 DFS/BFS 在二分图上反复寻找一条能翻转当前匹配状态的路径——即增广路。只要找到一条，匹配数就 +1；找不到，当前匹配就是最大匹配。

常见错误现象：match[y] = -1 初始没设对，导致第一次就跳过有效点；或者 DFS 返回 true 后没更新 match[y] 和 used[x]，结果匹配数卡在 0 或偏小。

• 必须初始化 match[] 数组为 -1（表示未匹配），不能用 0
• 每次 DFS 前重置 used[]（仅限当前轮次的左部点访问标记）
• DFS 函数返回 bool：找到增广路就返回 true，并在回溯中更新 match[y] 和 match[x]

DFS 版匈牙利算法模板要避开递归栈溢出和重复访问

当左部点数量大（比如 1e4）、图又稠密时，纯递归 DFS 容易爆栈或 TLE。关键不是“写得短”，而是控制访问边界和剪枝逻辑。

使用场景：稀疏二分图、左部点 ≤ 5000、需要代码简洁可读；不适用于左部点带权或要求字典序最小匹配。

立即学习“C++免费学习笔记（深入）”；

bool dfs(int x) {     for (int y : graph[x]) {         if (used[y]) continue;         used[y] = true;         if (match[y] == -1 || dfs(match[y])) {             match[y] = x;             return true;         }     }     return false; }

• used[y] 是右部点标记，每轮 DFS 前 memset 为 false，不能复用上一轮
• match[y] == -1 是终止条件之一，代表 y 尚未匹配，可直接占用
• 递归调用 dfs(match[y]) 是关键：尝试把原来匹配 y 的左部点 match[y] “腾”出来，给 x 让位

邻接表 vs 邻接矩阵：图存法直接影响性能和内存

邻接矩阵（vector<vector>> g</vector>）看似直观，但空间 O(V²)，且遍历每个右部点都要扫满列，实际复杂度接近 O(n³)。邻接表才是标配。

参数差异：graph[x] 存的是所有与左部点 x 相连的右部点编号（从 0 开始或 1 开始需统一），不是边权也不是是否可达。

• 右部点总数记作 m，左部点总数记作 n，数组 match 长度应为 m，下标对应右部点编号
• 若输入是 1-indexed 边（如 u v 表示左部 u 连右部 v），存图时记得 graph[u-1].push_back(v-1)
• 不要在 DFS 里反复调用 graph[x].size()，提前存进变量避免多次计算

匹配失败时 debug 要看三处：match 初始化、used 复位、图边方向

最常被忽略的是边方向反了——把右部点当成起点去连左部点，或者误以为 match[x] 存左部匹配，其实标准写法里 match[y] 才存右部点 y 匹配的左部点 x。

错误信息典型表现：match[y] 始终为 -1（图没建对）、dfs() 永远返回 false（used 没清或初始值错）、程序运行后匹配数为 0（左部点编号越界导致图没存进去）。

• 打印前几条边验证 graph[0] 是否非空，确认建图成功
• 检查 match 数组长度是否等于右部点总数，下标是否越界
• 确保 used 数组大小 ≥ 右部点总数，且每次调用 dfs 前用 memset(used, 0, sizeof used) 或 fill

事情说清了就结束