从棋盘覆盖到导弹防御3道LeetCode/ACWing真题带你玩转匈牙利算法建模匈牙利算法作为解决二分图最大匹配问题的经典方法在算法竞赛和面试中频繁出现。但很多学习者在掌握基础原理后面对实际问题时仍不知如何建立二分图模型。本文将通过三道典型题目——棋盘覆盖、車的放置和导弹防御塔深入剖析如何将现实问题抽象为二分图匹配问题并给出可复用的解题框架。1. 匈牙利算法核心思想回顾匈牙利算法的本质是通过寻找增广路来逐步扩大匹配。其核心操作可以概括为def hungarian(u): for v in graph[u]: if not visited[v]: visited[v] True if match[v] -1 or hungarian(match[v]): match[v] u return True return False算法的时间复杂度为O(nm)其中n为节点数m为边数。在实际编码中需要注意两个关键点visited数组需要在每次DFS前重置邻接表存储方式比邻接矩阵更节省空间2. 棋盘覆盖问题建模实战2.1 问题重述给定一个N×N的棋盘某些格子被禁止放置。需要用1×2的多米诺骨牌覆盖尽可能多的非禁止格子每个骨牌覆盖两个相邻格子。求最大覆盖数量。2.2 二分图建模思路0要素识别棋盘可以按照国际象棋棋盘样式进行黑白染色相邻格子颜色不同。同色格子之间没有边连接。1要素识别每个格子只能被一个骨牌覆盖对应二分图中每个节点只能有一条匹配边。建图步骤将黑色格子作为左部节点白色格子作为右部节点每个格子与其上下左右相邻的非禁止格子连边2.3 代码实现关键点int dir[4][2] {{0,1},{1,0},{0,-1},{-1,0}}; // 四个方向 bool dfs(int x, int y) { for(int i0; i4; i) { int nx x dir[i][0], ny y dir[i][1]; 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; }2.4 复杂度优化使用链式前向星存储邻接表对棋盘进行奇偶行列编号减少不必要的遍历3. 車的放置问题进阶分析3.1 问题描述在N×M棋盘上放置尽可能多的車要求不能放在禁止位置任意两个車不能同行或同列3.2 建模创新点不同于棋盘覆盖的行列约束这里需要将行和列都抽象为二分图的节点二分图组件对应问题元素左部节点所有行右部节点所有列边可放置位置3.3 多重约束处理当问题增加额外限制时如某些行/列最多放置k个車需要引入多重匹配的变形拆点法将每个行节点拆分为k个副本网络流法转化为最大流问题3.4 性能对比方法时间复杂度适用场景基础匈牙利O(nm)小规模数据(n,m≤500)拆点法O(knm)k较小时网络流O(n^2m)大规模复杂约束4. 导弹防御塔的多重匹配挑战4.1 问题复杂化导弹防御塔问题引入了时间维度约束单个炮台的多发能力导弹飞行时间计算4.2 分层建图技巧时间离散化通过二分答案确定每个炮台的发射次数p节点拆分将每个炮台拆分为p个时间层节点动态连边根据导弹能否在限定时间内命中目标建立边4.3 关键代码片段bool check(double mid) { int p (mid t2) / (t1 t2); // 计算最大发射次数 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 mid) { g[i].push_back((j-1)*p k); } } } } // 运行匈牙利算法 return max_match m; }5. 匈牙利算法建模的通用框架通过以上三个案例可以总结出二分图建模的通用流程识别二分图特性检查问题中是否存在自然的二分结构确认是否满足0要素和1要素确定节点划分左部节点通常表示主动选择方右部节点通常表示被动匹配方处理特殊约束多重匹配拆点或网络流动态约束二分答案分层图优化策略选择小规模数据基础匈牙利大规模数据Hopcroft-Karp或网络流在实际编程竞赛中建议准备以下模板基础匈牙利算法邻接矩阵版链式前向星版匈牙利拆点法处理多重匹配二分答案匈牙利框架
从棋盘覆盖到导弹防御：3道LeetCode/ACWing真题带你玩转匈牙利算法建模
发布时间：2026/6/1 4:17:49
从棋盘覆盖到导弹防御3道LeetCode/ACWing真题带你玩转匈牙利算法建模匈牙利算法作为解决二分图最大匹配问题的经典方法在算法竞赛和面试中频繁出现。但很多学习者在掌握基础原理后面对实际问题时仍不知如何建立二分图模型。本文将通过三道典型题目——棋盘覆盖、車的放置和导弹防御塔深入剖析如何将现实问题抽象为二分图匹配问题并给出可复用的解题框架。1. 匈牙利算法核心思想回顾匈牙利算法的本质是通过寻找增广路来逐步扩大匹配。其核心操作可以概括为def hungarian(u): for v in graph[u]: if not visited[v]: visited[v] True if match[v] -1 or hungarian(match[v]): match[v] u return True return False算法的时间复杂度为O(nm)其中n为节点数m为边数。在实际编码中需要注意两个关键点visited数组需要在每次DFS前重置邻接表存储方式比邻接矩阵更节省空间2. 棋盘覆盖问题建模实战2.1 问题重述给定一个N×N的棋盘某些格子被禁止放置。需要用1×2的多米诺骨牌覆盖尽可能多的非禁止格子每个骨牌覆盖两个相邻格子。求最大覆盖数量。2.2 二分图建模思路0要素识别棋盘可以按照国际象棋棋盘样式进行黑白染色相邻格子颜色不同。同色格子之间没有边连接。1要素识别每个格子只能被一个骨牌覆盖对应二分图中每个节点只能有一条匹配边。建图步骤将黑色格子作为左部节点白色格子作为右部节点每个格子与其上下左右相邻的非禁止格子连边2.3 代码实现关键点int dir[4][2] {{0,1},{1,0},{0,-1},{-1,0}}; // 四个方向 bool dfs(int x, int y) { for(int i0; i4; i) { int nx x dir[i][0], ny y dir[i][1]; 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; }2.4 复杂度优化使用链式前向星存储邻接表对棋盘进行奇偶行列编号减少不必要的遍历3. 車的放置问题进阶分析3.1 问题描述在N×M棋盘上放置尽可能多的車要求不能放在禁止位置任意两个車不能同行或同列3.2 建模创新点不同于棋盘覆盖的行列约束这里需要将行和列都抽象为二分图的节点二分图组件对应问题元素左部节点所有行右部节点所有列边可放置位置3.3 多重约束处理当问题增加额外限制时如某些行/列最多放置k个車需要引入多重匹配的变形拆点法将每个行节点拆分为k个副本网络流法转化为最大流问题3.4 性能对比方法时间复杂度适用场景基础匈牙利O(nm)小规模数据(n,m≤500)拆点法O(knm)k较小时网络流O(n^2m)大规模复杂约束4. 导弹防御塔的多重匹配挑战4.1 问题复杂化导弹防御塔问题引入了时间维度约束单个炮台的多发能力导弹飞行时间计算4.2 分层建图技巧时间离散化通过二分答案确定每个炮台的发射次数p节点拆分将每个炮台拆分为p个时间层节点动态连边根据导弹能否在限定时间内命中目标建立边4.3 关键代码片段bool check(double mid) { int p (mid t2) / (t1 t2); // 计算最大发射次数 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 mid) { g[i].push_back((j-1)*p k); } } } } // 运行匈牙利算法 return max_match m; }5. 匈牙利算法建模的通用框架通过以上三个案例可以总结出二分图建模的通用流程识别二分图特性检查问题中是否存在自然的二分结构确认是否满足0要素和1要素确定节点划分左部节点通常表示主动选择方右部节点通常表示被动匹配方处理特殊约束多重匹配拆点或网络流动态约束二分答案分层图优化策略选择小规模数据基础匈牙利大规模数据Hopcroft-Karp或网络流在实际编程竞赛中建议准备以下模板基础匈牙利算法邻接矩阵版链式前向星版匈牙利拆点法处理多重匹配二分答案匈牙利框架
