当前位置：首页 > news >正文

别再死记硬背匈牙利算法了！用这3道LeetCode/洛谷经典题，带你彻底搞懂二分图匹配

news 2026/6/1 10:05:08

二分图匹配实战：用3道经典题目彻底掌握匈牙利算法

在算法竞赛和面试中，二分图匹配是一个既基础又重要的知识点。很多学习者虽然理解了匈牙利算法的理论，但在实际解题时却不知如何将问题抽象为二分图模型。本文将带你通过三道经典题目，从实际问题出发，掌握识别二分图模型的关键技巧，真正理解匈牙利算法的应用场景。

1. 二分图匹配的核心要素

二分图匹配问题的关键在于识别"0要素"和"1要素"——这是将实际问题转化为二分图模型的两个核心特征。

0要素指的是节点能够被划分为两个独立的集合，且同一集合内的节点之间没有边相连。这意味着我们需要在问题中找到可以自然分为两类的对象，且同类对象之间不存在直接关联。

1要素则是指每个节点最多只能与一条匹配边相连。在大多数实际问题中，这表现为某种"一对一"的限制条件，比如一个资源只能分配给一个任务，或者一个位置只能放置一个物品。

理解这两个要素后，我们来看如何在实际问题中应用它们。

2. 棋盘覆盖问题

2.1 问题描述

给定一个N×N的棋盘，其中某些格子被禁止放置。现在要用1×2的多米诺骨牌覆盖棋盘，每个骨牌恰好覆盖两个相邻的格子，且不能覆盖禁止的格子。求最多可以放置多少个骨牌。

2.2 二分图建模

节点划分：将棋盘格子按照坐标(i+j)的奇偶性分为两类，形成二分图的两部分。例如，所有i+j为奇数的格子作为左部节点，偶数的作为右部节点。
边建立：对于每个可以放置的格子，如果它的相邻格子(上下左右)也可以放置，就在它们之间建立边。
匹配意义：每个骨牌覆盖两个相邻格子，对应二分图中的一条边。最大匹配就是最多可以放置的骨牌数量。

2.3 代码实现关键点

bool dfs(int x, int y) { for(int i=0; i<4; i++) { int nx = x + dir[i], 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; }

提示：在实现时，可以只对左部节点(如奇数坐标格子)进行DFS，这样可以减少一半的搜索量。

3. 車的放置问题

3.1 问题描述

在一个N×M的棋盘上放置尽可能多的車，要求它们互不攻击(即不在同一行或同一列)，且某些位置禁止放置。

3.2 二分图建模

节点划分：将行作为左部节点，列作为右部节点。
边建立：如果棋盘位置(i,j)可以放置車，就在行i和列j之间建立边。
匹配意义：每个匹配表示在(i,j)放置一个車，因为匹配保证了每行每列最多只有一个車。

3.3 与棋盘覆盖的区别

虽然都是棋盘问题，但建模方式完全不同：

棋盘覆盖：格子作为节点，相邻关系作为边
車的放置：行和列作为两类节点，可放置位置作为边

bool dfs(int i) { for(int j=1; j<=m; 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 i=1; i<=m; i++) { g[i].clear(); for(int j=1; j<=n; j++) { double flight_time = dist(i,j)/v; for(int k=1; k<=p; 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 i=1; i<=m; i++) { memset(vis, 0, sizeof(vis)); if(!dfs(i)) return false; } return true; }