别再死记硬背匈牙利算法了！用这3个趣味OJ题（棋盘覆盖、車的放置）彻底搞懂二分图匹配

匈牙利算法实战用棋盘覆盖与車的放置掌握二分图匹配在算法竞赛和面试中二分图匹配问题经常以各种变体出现。很多学习者虽然能背诵匈牙利算法的模板代码却在实际问题建模时束手无策。本文将通过三个经典OJ题目带你从零构建二分图匹配的思维模型。1. 二分图匹配的核心要素匈牙利算法解决的是二分图的最大匹配问题。理解以下两个核心要素是建模的关键0要素节点能分成两个独立集合集合内部没有边相连1要素每个节点只能与一条匹配边相连以棋盘覆盖问题为例我们可以将棋盘按照格子坐标和的奇偶性进行二染色。这样# 棋盘二染色示例 for i in range(n): for j in range(n): color (i j) % 2 # 0或1表示两种颜色这种染色方式确保了相邻格子颜色不同天然形成了二分图结构。2. 棋盘覆盖问题实战AcWing 372题给出了一个n×n的棋盘其中某些格子禁止放置。我们需要用1×2的骨牌覆盖尽可能多的格子。2.1 问题建模将棋盘二染色分为奇数格和偶数格每个可放置的格子作为一个节点相邻的可放置格子之间建立边关键转换骨牌覆盖匹配边最大骨牌数最大匹配数2.2 代码实现要点bool dfs(int x, int y) { for (int i 0; i 4; i) { // 四个方向 int nx x dir[i], ny y dir[i1]; if (invalid(nx, ny) || vis[nx][ny] || forbidden[nx][ny]) continue; vis[nx][ny] true; if (match[nx][ny] null || dfs(match[nx][ny].first, match[nx][ny].second)) { match[nx][ny] {x, y}; return true; } } return false; }注意事项只需从一个集合出发进行匹配如所有奇数格每次DFS前重置访问标记禁止格子需要特殊处理3. 車的放置问题精解AcWing 373题要求在棋盘上放置尽可能多的車且不能互相攻击。这实际上是N皇后问题的简化版。3.1 二分图建模技巧将问题转化为左部节点所有行右部节点所有列边表示该行该列可以放置車匹配的意义每个匹配表示在(i,j)放置一个車最大匹配最多可放置的車数3.2 实现优化bool dfs(int i) { for (int j 1; j m; j) { if (forbidden[i][j] || vis[j]) continue; vis[j] true; if (!match[j] || dfs(match[j])) { match[j] i; return true; } } return false; }性能对比方法时间复杂度空间复杂度回溯法O(n!)O(n²)匈牙利算法O(n³)O(n²)对于n200的规模匈牙利算法可以在1秒内完成而回溯法完全不可行。4. 导弹防御塔的多重匹配AcWing 374题引入了时间维度和多重匹配的概念。每个炮塔可以在不同时间发射多枚导弹。4.1 问题转化二分答案确定最短防御时间对每个炮塔拆分为多个时间点节点建立敌人与可达炮弹之间的边建模创新点将时间维度转化为节点复制二分答案匈牙利算法结合4.2 关键代码结构while (r - l 1e-9) { double mid (l r) / 2; int p calculate_max_shots(mid); // 构建二分图 for (每个敌人) { for (每个炮塔) { for (每次射击机会) { if (能在时间内击中) 添加边 } } } // 匈牙利算法 if (所有敌人都能匹配) r mid; else l mid; }复杂度分析二分次数约log(1e6/1e-9)≈50次每次匈牙利O(mnp)总复杂度O(50mn*p)5. 匈牙利算法的工程实践技巧在实际编码竞赛中匈牙利算法有以下常见优化邻接表优化对于稀疏图更高效vectorint adj[N];时间戳优化避免每次memsetint vis[N], timer; bool dfs(int u) { for (int v : adj[u]) { if (vis[v] timer) continue; vis[v] timer; // ... } } // 调用时 timer随机打乱避免最坏情况random_shuffle(adj[u].begin(), adj[u].end());性能对比测试数据规模基础实现时间戳优化打乱优化n500,m10001.2s0.8s0.6sn1000,m5000超时3.4s2.1s在解决实际问题时我习惯先画出二分图的结构草图。比如在棋盘覆盖问题中用不同颜色标记两类格子明确哪些是左部节点哪些是右部节点。这种可视化的方法能有效避免建模错误。