二分图匹配实战用3道经典题目彻底掌握匈牙利算法在算法竞赛和面试中二分图匹配是一个既基础又重要的知识点。很多学习者虽然理解了匈牙利算法的理论但在实际解题时却不知如何将问题抽象为二分图模型。本文将带你通过三道经典题目从实际问题出发掌握识别二分图模型的关键技巧真正理解匈牙利算法的应用场景。1. 二分图匹配的核心要素二分图匹配问题的关键在于识别0要素和1要素——这是将实际问题转化为二分图模型的两个核心特征。0要素指的是节点能够被划分为两个独立的集合且同一集合内的节点之间没有边相连。这意味着我们需要在问题中找到可以自然分为两类的对象且同类对象之间不存在直接关联。1要素则是指每个节点最多只能与一条匹配边相连。在大多数实际问题中这表现为某种一对一的限制条件比如一个资源只能分配给一个任务或者一个位置只能放置一个物品。理解这两个要素后我们来看如何在实际问题中应用它们。2. 棋盘覆盖问题2.1 问题描述给定一个N×N的棋盘其中某些格子被禁止放置。现在要用1×2的多米诺骨牌覆盖棋盘每个骨牌恰好覆盖两个相邻的格子且不能覆盖禁止的格子。求最多可以放置多少个骨牌。2.2 二分图建模节点划分将棋盘格子按照坐标(ij)的奇偶性分为两类形成二分图的两部分。例如所有ij为奇数的格子作为左部节点偶数的作为右部节点。边建立对于每个可以放置的格子如果它的相邻格子(上下左右)也可以放置就在它们之间建立边。匹配意义每个骨牌覆盖两个相邻格子对应二分图中的一条边。最大匹配就是最多可以放置的骨牌数量。2.3 代码实现关键点bool dfs(int x, int y) { for(int i0; i4; i) { int nx x dir[i], ny y dir[i1]; if(/* 边界检查 */ || /* 禁止格子检查 */ || vis[nx][ny]) continue; vis[nx][ny] true; if(match[nx][ny].first -1 || dfs(match[nx][ny].first, match[nx][ny].second)) { match[nx][ny] {x, y}; return true; } } return false; }提示在实现时可以只对左部节点(如奇数坐标格子)进行DFS这样可以减少一半的搜索量。3. 車的放置问题3.1 问题描述在一个N×M的棋盘上放置尽可能多的車要求它们互不攻击(即不在同一行或同一列)且某些位置禁止放置。3.2 二分图建模节点划分将行作为左部节点列作为右部节点。边建立如果棋盘位置(i,j)可以放置車就在行i和列j之间建立边。匹配意义每个匹配表示在(i,j)放置一个車因为匹配保证了每行每列最多只有一个車。3.3 与棋盘覆盖的区别虽然都是棋盘问题但建模方式完全不同棋盘覆盖格子作为节点相邻关系作为边車的放置行和列作为两类节点可放置位置作为边bool dfs(int i) { for(int j1; jm; j) { if(禁止放置[i][j] || vis[j]) continue; vis[j] true; if(!match[j] || dfs(match[j])) { match[j] i; return true; } } return false; }4. 导弹防御塔问题4.1 问题描述有n个防御塔和m个敌人每个防御塔可以发射多枚导弹但发射间隔为t1导弹飞行时间为t2。求消灭所有敌人的最短时间。4.2 二分图建模节点划分敌人作为左部节点防御塔的发射时间点作为右部节点。多重匹配每个防御塔可以发射多枚导弹因此需要拆点处理。时间因素通过二分法确定最短时间在每个时间点检查是否所有敌人都能被覆盖。4.3 解决思路二分可能的时间T计算每个防御塔在时间T内最多能发射的导弹数p将每个防御塔拆分为p个节点每个代表一个发射时间点如果敌人在某导弹的射程和时间范围内就建立边检查是否存在完美匹配bool check(double T) { int p (T t2) / (t1 t2); // 计算最多发射次数 p min(p, m); // 建立二分图 for(int i1; im; i) { g[i].clear(); for(int j1; jn; j) { double flight_time dist(i,j)/v; for(int k1; kp; k) { double total_time flight_time t1*k t2*(k-1); if(total_time T) { g[i].push_back((j-1)*p k); } } } } // 匈牙利算法检查完美匹配 memset(match, 0, sizeof(match)); for(int i1; im; i) { memset(vis, 0, sizeof(vis)); if(!dfs(i)) return false; } return true; }5. 常见问题与优化技巧5.1 如何快速识别二分图问题寻找可以自然分为两类的对象检查是否存在一对一或一对多的限制关系常见场景任务分配、资源调度、棋盘覆盖等5.2 匈牙利算法优化邻接表优化对于稀疏图使用邻接表存储预处理匹配对于明显可以匹配的节点先处理随机化搜索顺序有时可以加快找到增广路的速度5.3 其他应用场景稳定婚姻问题任务分配问题网络流量中的最大流问题(作为特例)在实际刷题过程中我发现很多看似复杂的问题一旦识别出二分图模型就能用匈牙利算法轻松解决。关键在于培养识别0要素和1要素的直觉这需要通过大量练习来积累经验。