1. 项目概述为什么二分图值得你花时间彻底搞懂如果你刷过一些算法题或者接触过图论大概率听说过“二分图”这个词。它听起来有点学术但实际应用场景却出奇地广泛从社交网络的好友推荐、到任务调度、再到编译器优化背后都可能藏着二分图的思想。我最初接触它时觉得就是个“把点分成两堆”的简单概念直到在解决实际问题时反复碰壁才意识到自己对它的理解有多肤浅——比如为什么用染色法就能判断匈牙利算法那看似“腾挪”的步骤到底在干什么最小点覆盖和最大匹配为什么相等这份整理源于我多次在项目中和面试里被二分图相关难题“教育”后的复盘。它不是教科书式的定义罗列而是一个从业者视角的深度拆解从最核心的“二分性”判定到解决匹配问题的“匈牙利算法”这一利器再到几个关键定理最大匹配、最小点覆盖等的串联与应用。我会用大量模拟题目的场景一步步带你推演把每个算法背后的“为什么”讲透并分享那些容易栽跟头的细节和调试技巧。无论你是正在备战技术面试还是需要在开发中处理类似的匹配、分配问题这份从概念到实战的全面梳理应该能帮你把这块知识真正变成自己的工具。2. 核心概念拆解二分图究竟是什么又如何判定2.1 二分图的定义与直观理解我们先抛开严谨的数学定义用最直白的话来说二分图是一种特殊的图你能把它所有的顶点分成两个独立的集合比如左集和右集并且保证每条边的两个端点都分别属于这两个不同的集合。换句话说在同一个集合内的顶点之间是绝对没有边直接相连的。这个概念最生活化的类比就是“相亲派对”假设会场里有两群人一边全是男生一边全是女生。一条边就表示一位男生和一位女生彼此有意向认识。在这个模型里绝对不会出现“男生和男生之间有意向”或者“女生和女生之间有意向”的边假设派对规则如此。这就是一个典型的二分图。形式化定义一个图 G(V, E) 是二分图当且仅当存在顶点集 V 的一个划分 (X, Y)即 X ∪ Y V 且 X ∩ Y ∅使得对于每一条边 e(u, v) ∈ E都有 u ∈ X 且 v ∈ Y或者 u ∈ Y 且 v ∈ X。理解这个定义的关键在于“划分”和“约束”。它并不要求图是连通的多个连通分量可以各自构成二分图。它核心约束的是边的连接方式。注意二分图关注的是顶点之间的连接关系拓扑结构与顶点的位置、边的长短曲直无关。即使一个图画出来交叉很多只要它能满足上述划分条件它就是二分图。2.2 二分图的判定方法染色法深度剖析给定一个具体的图通常以邻接表或邻接矩阵形式给出我们如何判断它是否是二分图呢最经典、最实用的方法是染色法也称为二着色问题。算法核心思想模拟上述划分过程。我们尝试用两种颜色比如颜色1和颜色2给所有顶点染色。规则是相邻的顶点必须染成不同的颜色。如果从任意一个顶点出发能成功给所有顶点染色且不违反规则那么这个图就是二分图如果在染色过程中发现某个相邻顶点已经被染成了和自己相同的颜色则说明无法划分该图不是二分图。这个过程本质上是一次或多次**深度优先搜索DFS或广度优先搜索BFS**的遍历。因为图可能不连通我们需要检查每一个连通分量。为什么染色法有效其正确性基于一个关键定理一个图是二分图当且仅当它不包含长度为奇数的环奇环。如果图是二分图所有环都必须经过左右集交替因此环的顶点数即环的长度必然是偶数。反之如果图没有奇环那么通过DFS/BFS染色就一定不会冲突从而成功划分。染色法正是在检测奇环的存在。当发现相邻节点颜色相同时就说明当前路径加上这条边形成了一个奇环。DFS实现染色法的详细步骤与代码心经初始化定义一个数组color[]大小为顶点数n初始值设为0表示未染色。同时可以定义一个全局布尔变量isBipartite初始为true。遍历所有顶点对于每个顶点i如果color[i] 0说明它属于一个尚未访问的连通分量则从它开始进行DFS/BFS染色假设将其染成颜色1。DFS递归函数dfs(u, c)将顶点u染成颜色c。遍历u的所有邻居顶点v如果color[v] 0说明v未染色则递归调用dfs(v, 3-c)。这里3-c是一个小技巧如果c是1那么3-c就是2如果c是2那么3-c就是1。这实现了颜色交替。如果color[v] ! 0且color[v] c说明邻居v已经被染成了和u相同的颜色违反了二分图定义。立即将isBipartite设为false并返回可以进一步优化直接终止所有递归。结果判断遍历结束后检查isBipartite的值。// 以C邻接表为例 #include vector using namespace std; class Solution { public: bool isBipartite(vectorvectorint graph) { int n graph.size(); vectorint color(n, 0); // 0:未染色1:颜色12:颜色2 for (int i 0; i n; i) { if (color[i] 0) { // 遇到未染色的连通分量起点 if (!dfs(graph, color, i, 1)) { return false; } } } return true; } private: bool dfs(vectorvectorint graph, vectorint color, int u, int c) { color[u] c; for (int v : graph[u]) { if (color[v] 0) { // 如果邻居未染色染成相反颜色继续递归 if (!dfs(graph, color, v, 3 - c)) { return false; } } else if (color[v] c) { // 邻居已染色且颜色相同冲突 return false; } // 邻居已染色且颜色不同无事发生继续检查下一个邻居 } return true; } };实操心得与避坑指南图可能不连通这是最容易遗漏的点必须遍历每个顶点作为可能的DFS起点而不能只从0号顶点开始。上面的代码通过外层循环for (int i 0; i n; i)解决了这个问题。递归深度对于顶点数非常多例如10^5级别的图DFS递归可能导致栈溢出。此时可以改用BFS的迭代队列实现或者调整编译器的栈大小。BFS版本逻辑完全一致只是将递归栈换成了队列。颜色标记技巧使用3-c来取反颜色比c 1 ? 2 : 1更简洁。也可以使用-1和1两种颜色通过取负来实现反转。性能考量算法的时间复杂度是 O(VE)其中V是顶点数E是边数因为每个顶点和每条边都只访问了一次。空间复杂度主要是存储图的邻接表 O(VE) 和颜色数组 O(V)。3. 匈牙利算法求解二分图最大匹配的利器当我们确认一个图是二分图后最常遇到的问题就是“匹配”。什么是匹配简单说就是在图中选出一些边使得这些边两两之间没有公共顶点。就像一个男生只能和一个女生牵手一条边一个女生也只能和一个男生牵手。最大匹配就是找到这样一个边集使得其包含的边数最多。匈牙利算法就是解决二分图最大匹配问题的经典算法。它由匈牙利数学家提出核心思想是“腾挪”或“回溯”通过寻找“增广路径”来不断增加匹配数。3.1 算法核心思想寻找增广路径要理解匈牙利算法必须先理解“增广路径”这个概念。交替路从一个未匹配点出发依次经过“非匹配边 - 匹配边 - 非匹配边 - ...”形成的路径。增广路一条起点和终点都是未匹配点的交替路。增广路有一个重要特性将路径上所有的匹配边和非匹配边互换即“反转”匹配边数就会恰好增加1。因为路径两端都是未匹配点反转后原来路径上的第一个和最后一个非匹配边变成了匹配边而内部的匹配边变成了非匹配边匹配边总数增加了1。匈牙利算法就是一个不断寻找增广路并反转直到找不到增广路为止的过程。根据Berge定理此时得到的匹配就是最大匹配。3.2 算法步骤详解与模拟推演假设我们有一个二分图左集为男生集合 U右集为女生集合 V。我们通常固定从左集出发去寻找匹配。算法步骤初始化所有顶点均未匹配。遍历左集每个顶点 u尝试为 u 寻找一个匹配的右集顶点 v。为 u 寻找匹配的过程DFS函数find(u)遍历 u 所有心仪的即相连的女生 v。如果女生 v 在本轮尝试中还未被考虑过需要一个visited数组记录本轮状态则标记 v 已被考虑。检查 v 的当前状态情况Av 还未匹配。太好了直接将 u 与 v 匹配。返回成功。情况Bv 已经匹配了某个男生 u‘。那么我们需要尝试“挖墙脚”递归调用find(u‘)看看能否为 u‘ 找到一个新的女生 v’ 来匹配。如果find(u‘)成功了那么 u’ 就让出了 vu 就可以和 v 匹配了。这正体现了“腾挪”的思想。如果所有心仪的女生都尝试过了还是无法为 u 找到匹配则返回失败。统计结果成功为左集一个顶点找到匹配总匹配数就加一。让我们模拟一个简单例子 左集男生 A, B, C 右集女生 X, Y, Z 边A-X, A-Y, B-X, B-Y, C-Y为A找匹配尝试XX未匹配成功。匹配(A-X)为B找匹配尝试XX已匹配A。递归为A找新匹配A尝试YY未匹配成功。于是A改为匹配YB匹配X。匹配(A-Y), (B-X)为C找匹配尝试YY已匹配A。递归为A找新匹配A尝试XX已匹配B。递归为B找新匹配B尝试YY已匹配A形成循环依赖且B没有其他边。递归失败。C尝试Y失败Y在本轮visited中。C没有其他边匹配失败。 最终最大匹配为2。3.3 代码实现与关键细节#include vector using namespace std; class Hungarian { private: vectorvectorint graph; // 邻接表graph[u] 存储左顶点u连接的右顶点 vectorint matchR; // matchR[v] 记录右顶点v匹配的左顶点编号-1表示未匹配 vectorbool visited; // visited[v] 记录在本轮DFS中右顶点v是否被访问过 public: Hungarian(int nLeft, int nRight) { graph.resize(nLeft); matchR.assign(nRight, -1); } void addEdge(int u, int v) { graph[u].push_back(v); } bool dfs(int u) { for (int v : graph[u]) { if (!visited[v]) { visited[v] true; // 如果女生v没对象或者可以为她现在的对象找到新欢 if (matchR[v] -1 || dfs(matchR[v])) { matchR[v] u; // 匹配成功 return true; } } } return false; // 尝试了所有意向女生都失败了 } int maxMatch() { int matchCount 0; for (int u 0; u graph.size(); u) { visited.assign(matchR.size(), false); // 每一轮重置访问标记 if (dfs(u)) { matchCount; } } return matchCount; } };关键细节与性能分析visited数组的作用与重置这是算法正确性的关键。visited[v]表示在本轮为某个特定左顶点u寻找匹配的DFS过程中右顶点v是否已经被探索过。它的目的是防止在递归中陷入死循环重复探索同一个右顶点。必须在为每一个新的左顶点u开始寻找匹配前重置整个visited数组。时间复杂度最坏情况下需要为左集每个顶点O(V)执行一次DFS每次DFS可能遍历所有边O(E)。因此朴素匈牙利算法的时间复杂度是O(V*E)。对于稠密图这个复杂度较高。存在基于BFS的Hopcroft-Karp算法可以将复杂度优化到 O(√V * E)适用于大规模二分图。空间复杂度主要是存储邻接表 O(VE)以及matchR和visited数组 O(V)。一个常见误解认为匈牙利算法只能处理“左边每个顶点只连少数边”的情况。实际上它适用于任意二分图只是复杂度与边数线性相关。在建模时如果左集或右集非常大需要考虑优化建图。实操心得在竞赛或面试编码时务必注意图的顶点编号是从0开始还是1开始并相应调整数组大小。visited数组重置的写法visited.assign(n, false)比写一个for循环更清晰。另外如果左集和右集顶点编号有重叠一定要用两个不同的数组来区分或者在建模时就做好偏移。4. 二分图相关的重要定理与应用模型掌握了判定和最大匹配算法二分图的理论核心还在于几个优美的定理它们将不同概念联系起来是解决复杂问题的钥匙。4.1 四大定理及其关联最大匹配我们已经详细讨论使用匈牙利算法求解。最小点覆盖选取最少的顶点使得图中每条边都至少有一个端点被选中。König定理指出在二分图中最大匹配的边数 最小点覆盖的顶点数。这是一个非常强大且反直觉的结论它意味着你可以通过求解最大匹配来间接得到最小点覆盖的方案。最大独立集选取最多的顶点使得这些顶点之间两两没有边相连。在二分图中最大独立集的顶点数 总顶点数 - 最小点覆盖的顶点数。因为“点覆盖”和“独立集”是互补的概念覆盖了所有边的点剩下的点自然就是一个独立集。最小路径覆盖有向无环图DAG用最少的不相交的路径覆盖DAG的所有顶点。可以通过将DAG转化为二分图来求解将每个顶点i拆成出点i和入点i’如果原图有边 i-j则在二分图中连边 i - j’。那么最小路径覆盖数 原图顶点数 - 转化后二分图的最大匹配数。这些定理构成了一个紧密的网络。通常我们通过匈牙利算法求出最大匹配数然后利用等式关系去求解其他问题。4.2 经典问题建模实战理解定理的最好方式就是应用。下面看几个经典建模。问题一棋盘覆盖问题在一个N*N的棋盘上有些格子禁止放置。问最多能放置多少个“车”国际象棋中的Rook使得它们互不攻击即不在同一行或同一列。建模将每一行看作左集的一个顶点每一列看作右集的一个顶点。对于一个允许放置的格子(i, j)就在左顶点i和右顶点j之间连一条边。放置一个车在(i, j)就相当于占据了第i行和第j列。问题转化为选出一些边放置车使得这些边没有公共顶点车不互相攻击。这正是二分图的最大匹配问题。最大匹配数就是最多能放置的车数。问题二任务分配问题有m个任务和n个工人每个工人有能力完成某些任务但每个工人同一时间只能做一个任务每个任务也只能由一个工人完成。问最多能完成多少个任务建模工人作为左集任务作为右集。如果工人i能完成任务j则连边。这直接就是最大匹配问题。问题三最小顶点覆盖应用一个城市有若干条道路连接两个区域现在要设置最少的监控摄像头要求每条道路至少有一端被监控。求最少摄像头数。建模道路是边道路两端的区域是顶点集合。由于道路只连接两个不同区域这天然是一个二分图。最少摄像头数就是最小点覆盖。根据König定理先求最大匹配数该数即为答案。更进一步匈牙利算法在运行结束后可以通过未匹配点出发进行交替遍历标记出最小点覆盖的具体方案S集中的未标记点和T集中的已标记点。问题四最大独立集应用一个公司有若干员工有些员工之间关系不好不能同时留下。要裁员希望留下最多的人且留下的人之间关系都好。建模如果员工矛盾关系可以抽象为二分图例如矛盾只发生在两个部门之间那么留下的最大人数就是最大独立集。先求最大匹配得到最小点覆盖数再用总人数减去它即可。4.3 定理证明思路与理解虽然在实际编程中我们可能不需要手动证明但理解证明思路能极大加深认知。以König定理最大匹配 最小点覆盖为例其构造性证明思路是用匈牙利算法求出最大匹配M。从左集所有未匹配点出发进行交替路遍历只能走未匹配边-匹配边-未匹配边...。标记所有在遍历过程中访问到的顶点。令最小点覆盖集为左集中未被标记的顶点∪右集中被标记的顶点。可以证明(a) 这个集合的确覆盖了所有边。(b) 集合大小恰好等于匹配数M。(c) 不存在更小的点覆盖集。这个证明过程也直接给出了由最大匹配构造最小点覆盖方案的算法非常巧妙。5. 匈牙利算法的优化、变种与实战调试5.1 基础匈牙利算法的局限性我们之前实现的DFS版本匈牙利算法时间复杂度为O(V*E)。当顶点和边数达到10^4级别时就可能面临性能压力。其主要瓶颈在于每次为一个左顶点寻找增广路时都可能进行一遍全图DFS即使很多边已经被证明在当前匹配下无法增广。5.2 Hopcroft-Karp算法基于BFS的多路增广Hopcroft-Karp算法是匈牙利算法的优化版本核心思想是使用BFS一次找到多条长度最短的增广路然后用DFS沿这些路径同时增广从而大幅减少寻找增广路的次数。算法步骤BFS分层从左集所有未匹配点出发进行BFS建立到达右集顶点的距离层数关系。目的是找到所有长度最短的增广路。DFS多路增广从左集每个未匹配点出发按照BFS建立的距离层次进行DFS寻找增广路。由于BFS保证了找到的是最短路径DFS可以沿着这些预定路线高效地完成多条互不相交的增广路的增广。重复重复步骤1和2直到BFS无法找到任何增广路为止。该算法的时间复杂度可以优化到O(√V * E)在处理大规模稀疏二分图时优势明显。// Hopcroft-Karp算法框架示意代码较长此处给出核心逻辑 class HopcroftKarp { vectorvectorint adj; vectorint dist, matchL, matchR; // dist用于BFS分层 int nLeft, nRight; bool bfs() { // 从左集未匹配点开始BFS构建层次图 // 如果发现右集未匹配点说明存在增广路 } bool dfs(int u) { // 按照层次图进行DFS增广 } public: int maxMatch() { int matching 0; while (bfs()) { for (int u 0; u nLeft; u) { if (matchL[u] -1 dfs(u)) { matching; } } } return matching; } };5.3 带权二分图与KM算法前面讨论的都是最大匹配数量但现实中很多问题需要考虑“权重”。例如在任务分配中不同工人完成不同任务的效率收益不同我们希望在完成最大匹配人人有活干的同时使得总收益最大。这就是最大权完美匹配问题。解决此问题的经典算法是Kuhn-Munkres算法KM算法。它通过维护顶标一个对顶点赋予的权值和相等子图的概念将最大权匹配问题转化为普通最大匹配问题来迭代求解。KM算法要求二分图是完全二分图左右顶点数相等且所有边都存在对于不存在的边可以赋予负无穷或0权重来处理。KM算法的核心步骤是初始化顶标、用匈牙利算法在相等子图中找完美匹配、若找不到则调整顶标扩大相等子图直到找到为止。其时间复杂度为O(V^3)。注意KM算法求解的是最大权完美匹配即要求匹配数达到最大完美匹配。如果只要求最大权匹配而不要求完美问题会有所不同可能需要使用其他费用流模型。5.4 实战调试技巧与常见问题排查在实现匈牙利算法时以下几个问题是高频错误点visited数组重置错误这是最最常见的错误。必须理解visited数组是针对单轮DFS的用于防止在为一特定左顶点找增广路时重复访问右顶点。因此for (int u...)循环的每一次迭代开始都必须重置visited。错误示例将visited数组定义为全局布尔数组但在DFS函数中只标记不重置导致后续搜索被错误地限制。正确做法如示例代码所示在maxMatch函数中对每个左顶点u调用dfs(u)前执行visited.assign(nRight, false)。图存储错误确保邻接表graph的索引含义清晰。graph[u]存储的是左顶点u连接的右顶点编号。如果题目给的编号是1-based需要转换为0-based。递归栈溢出对于顶点数上万的大图DFS递归深度可能很大。可以改用栈模拟递归或使用BFS版本的匈牙利算法虽然复杂度相同但避免了递归。Hopcroft-Karp算法天然使用BFS/DFS结合也能缓解此问题。多组数据未清空在有多组测试数据时忘记清空全局的graph、matchR等数组导致上一组数据污染下一组。误用算法KM算法只能用于最大权完美匹配。如果只是求最大匹配数用匈牙利或Hopcroft-Karp即可。如果求最大权匹配但不一定完美可能需要用最小费用最大流。调试建议从小例子开始手动模拟画出二分图一步步跟踪算法执行过程比对matchR数组的变化。打印关键的中间状态比如每轮DFS开始前的visited重置情况以及每次成功匹配后的matchR数组。对于复杂问题先确保二分图建模是正确的。可以尝试用染色法验证图的二分性。6. 从理论到应用典型题目分析与举一反三理论学习之后我们通过分析几道经典题目来看如何将实际问题抽象成二分图模型并选择合适的算法解决。6.1 题目一LeetCode 785. 判断二分图这是最直接的二分图判定应用题。题目给定一个无向图以邻接表形式判断它是否是二分图。解法直接使用我们第二部分讲解的染色法DFS/BFS。这是标准解法时间复杂度O(VE)。关键在于处理好图可能不连通的情况。举一反三如果题目问“最少删除多少条边可以使图变成二分图”问题就变成了寻找图中的奇环。这通常需要更深入的图论知识但核心仍然是二分图判定的变形。6.2 题目二LeetCode 886. 可能的二分法题目描述有N个人编号从1到N。给定一个数组dislikes其中dislikes[i] [a, b]表示a和b不能分在同一组。要求判断能否将所有人分成两组使得每组内任意两人都没有 dislike 关系。建模与分析每个人是一个顶点。dislike关系构成边。分组要求同一个组内不能有边。这等价于要求所有边连接的两个顶点必须在不同的组。这正是二分图的定义问题转化为判断这个由dislike关系构成的图是否是二分图。解法直接使用染色法。如果染色成功则可以分组如果冲突则不能。心得这道题完美展示了如何将“分组矛盾”问题转化为二分图判定。关键在于理解“组内无关系”等价于“关系边必须跨越两组”。6.3 题目三AcWing 861. 二分图的最大匹配模板题这是纯粹的匈牙利算法模板题。给定一个二分图求其最大匹配数。解法直接套用匈牙利算法DFS版本或Hopcroft-Karp算法。需要注意输入格式通常左集和右集顶点是分开编号的或者需要自己划分。这是练习算法实现的绝佳题目。扩展题目可能会要求输出具体的匹配方案而不仅仅是数量。这只需要在算法结束后输出matchR数组即可对于每个右顶点v如果matchR[v] ! -1则说明它与左顶点matchR[v]匹配。6.4 题目四棋盘覆盖的变种——骨牌覆盖问题在一个有障碍物的N*M棋盘上用1x2的骨牌覆盖所有无障碍格子骨牌不能重叠不能覆盖障碍物。问最多能放多少骨牌建模将棋盘黑白染色像国际象棋棋盘一样。可以发现一个1x2的骨牌必然覆盖一个黑格和一个白格。将黑格作为左集顶点白格作为右集顶点。如果两个相邻格子上下左右都是无障碍的且一黑一白则在它们对应的顶点间连一条边。一个骨牌对应一条边且骨牌不重叠意味着选出的边没有公共顶点因为一个格子只能属于一个骨牌。问题转化为在这个二分图中找最大匹配。最大匹配数就是最多能放的骨牌数。解法使用匈牙利算法求解。顶点数最多NM边数最多4N*M每个格子最多有4个邻居。需要注意障碍物的处理以及将二维坐标映射到一维顶点编号的技巧。心得这道题是二分图建模的经典。其核心洞察是棋盘黑白染色后骨牌必然连接异色格从而自然形成二分图。这种“染色发现二分性”的思路在很多网格问题中都有应用。6.5 复杂建模综合题问题一个项目有多个任务每个任务需要两种不同的技能。现有若干员工每个员工掌握若干技能。一个员工同一时间只能参与一个任务一个任务需要两个不同的员工来完成各贡献一种技能。问最多能完成多少个任务建模步骤任务是需要完成的目标。难点在于一个任务需要两个员工且技能不同。我们可以将每个任务拆解成两个需求需求A需要技能1需求B需要技能2。但是这两个需求必须由不同的员工满足。一种巧妙的建模是以员工为顶点以任务为桥梁。考虑构建这样一个二分图左集是所有员工右集也是所有员工其实是同一批人的两个副本。对于一个任务需要技能S1和S2我们找出所有掌握技能S1的员工集合U1和所有掌握技能S2的员工集合U2。然后在二分图中为U1中的每个员工作为左顶点和U2中的每个员工作为右顶点之间连一条边这条边代表“可以合作完成该任务”。但这里有个问题一条边无法区分是哪个任务。更标准的建模是使用“任务”作为中间点的三分图或者使用更通用的网络流模型会更清晰。实际上这是一个二分图带容量匹配的变种或者可以直接用最大流建模源点 - 员工 - 任务拆点- 员工 - 汇点并设置合理的容量。经过分析更精确的二分图建模可以是将“任务”作为边。但一个任务连接两个员工这不是二分图的边二分图边连接左右不同集。所以需要转化为每个任务创建一个虚拟的“任务节点”这会让图变成三分。由此可见并非所有匹配问题都能直接套用标准二分图模型。当约束更复杂时如一个任务需要多个资源可能需要更强大的网络流模型。二分图最大匹配实际上是网络流中最大流问题的一个特例所有边容量为1。掌握二分图是理解更复杂网络流模型的基础。面对复杂问题建模步骤应该是识别“对象”和“匹配关系”。判断对象是否能自然分成两类左集/右集。判断匹配关系边是否是一对一的。如果满足尝试二分图建模如果不满足如多对一、一对多、多重约束考虑使用网络流。二分图相关的内容从基础概念到核心算法再到进阶定理和实战应用构成了一个自洽且强大的工具箱。我个人的体会是理解二分图的关键在于抓住其“划分”和“匹配”的本质。染色法是判断划分的尺子匈牙利算法是寻找最优匹配的引擎而几个核心定理则是连接不同问题的桥梁。在实战中多思考如何将问题中的“冲突”、“合作”、“分配”关系抽象成“边”将实体抽象成“点”并判断其是否具备二分性是运用这套理论的第一步。当标准二分图模型无法满足时要知道它的上限在哪并自然过渡到网络流等更一般的工具。把这套逻辑理顺了再遇到相关的题目思路就会清晰很多。