带集训队这几年我发现一个很有意思的现象很多学生C语法学得挺扎实指针、STL、排序都能写可一碰到CSP-S提高组的图论题就卡住——倒不是不知道最短路和最小生成树而是遇到一类题它不说自己是图论题题干里没有“图”字但真正的解法却指向同一个方向二分图。二分图在信奥赛C提高组里属于“考纲明列、暗考频繁”的知识点。从初赛选择题里“判断图是否为二分图”的性质题到复赛里“把新场景建模成二分图”的大题几乎隔一两年就会以各种面目出现。它自身的知识点其实不多核心就三块染色法判定、最大匹配、以及由匹配导出的最小点覆盖/最大独立集/最小路径覆盖。真正难的地方从来不是背模板而是题目不会直接告诉你“这是二分图请跑匈牙利”你需要从排班、棋盘、分组、冲突这些叙事里把模型剥出来。这篇文章就围绕这条主线展开CSP-S里怎么识别二分图、怎么用染色法和匈牙利算法把它做出来以及我最常看到学生踩的坑。不管你是第一次冲提高组还是已经拿过省一想补短板照着本文的模板和建模思路走一遍基本能把二分图这块吃透。1. 先搞清楚二分图在CSP-S里到底怎么考1.1 二分图是什么用一句话说透二分图的定义很简单一个无向图顶点能分成两个互不相交的集合A和B使得图中每条边的两个端点一个在A、一个在B。换句话说集合内部不允许连边。它有三个等价的表述考场上哪个方便用哪个顶点可以二染色相邻顶点颜色不同图中不存在长度为奇数的环奇环所有回路长度都是偶数。很多同学对第二个表述不敏感但初赛特别爱考。给你一个图问它是不是二分图你下意识想“能不能分成两拨人”其实更快的方法是找有没有奇环有奇环一定不是没有奇环一定是。这个结论对后面设计算法至关重要。1.2 初赛和复赛的考法完全不同初赛第一轮考的是概念和性质。常见的有这么几种出法给一个具体图判断它是不是二分图问“判断一个图是否为二分图可以使用的算法是”——答案本质上是DFS/BFS染色判断题“一个图含有奇数环则它一定不是二分图”这种是送分题复杂度的判断染色法判断二分图的时间复杂度。复赛第二轮不考裸概念而是把二分图包在一层场景下面。我印象里近几年提高组的图论题越来越不爱出“裸板子”而是喜欢给你一个看起来像贪心、像搜索、甚至像数据结构的场景最后用二分图模型一收。所以只背模板不够建模能力才是复赛二分图题的分水岭。1.3 数据范围是判断题目意图的第一信号做题先看数据范围这在二分图题里尤其准n ≤ 500边数在 n² 量级大概率是匈牙利算法O(VE) 能过n ≤ 10⁵但要求“判断是否可行/最小化最大值”很可能是二分答案 O(n m) 染色法判定n ≤ 20可能是状态压缩但若题目里明显有两类对象也要考虑是不是二分图模型题目出现“每行最多选一个”“每个任务分配给一个人”“两种颜色”“两个监狱”这类措辞直接往二分图上想。一个比较反直觉的经验是CSP-S里二分图的题数据范围经常会开得“刚好卡住搜索但又没卡死”原因是出题人希望你想出O(nm)或O(VE)级别的算法而不是DFS爆搜。遇到这类范围思路往图论模型上靠成功率会高很多。2. 染色法判定二分图模板背后的三条逻辑链2.1 为什么“无奇环”是判定的核心染色法的思路很朴素随便选一个点染成黑色它的所有邻居染成白色邻居的邻居染成黑色……如果过程中发现一条边的两个端点已经被染成了同一种颜色说明矛盾这个图不是二分图。这个算法背后的逻辑链值得想明白如果图是二分图从任一顶点出发它所在集合就确定了同一集合内的点必须同色跨集合的点必须异色。所以染色的结果是唯一的每个连通分量内只有两种互斥方案。如果染色失败说明存在一条边两端同色。沿着DFS树看这条边会和一个树上的路径拼成一个环。树上的相邻节点颜色必然交替一条路径如果从某个颜色出发回到同色节点需要的步数是偶数再加上这条同色边环的总长度就是奇数。所以染色失败 存在奇环 不是二分图。反过来无奇环的图一定能染色成功这就是等价性。理解了这层你就不会在“到底要不要处理重边”“孤立点怎么办”这种细节上空耗重边不影响二染色孤立点随便染。2.2 DFS模板和两个“看起来对但必错”的写法直接上一份我平时给集训队用的模板#include bits/stdc.h using namespace std; const int MAXN 100005; vectorint G[MAXN]; int color[MAXN]; // 0表示未染色1和-1表示两种颜色 bool dfs(int u, int c) { color[u] c; for (int v : G[u]) { if (color[v] c) return false; // 相邻点同色 if (color[v] 0 !dfs(v, -c)) return false; } return true; } bool isBipartite(int n) { memset(color, 0, sizeof(color)); for (int i 1; i n; i) { if (color[i] 0 !dfs(i, 1)) { return false; } } return true; }这份模板有两个细节我必须强调因为几乎每周都有学生在这栽跟头。第一个错误只从1号点开始DFS没有遍历所有连通分量。图可能不连通一个连通分量染色成功不代表整个图是二分图。必须像上面这样用循环遍历所有未染色的起点。第二个错误用bool的color数组初始化全为false然后染完0号色和1号色都是“true”结果无法区分“没访问过”和“访问过且是0号颜色”。解决办法就是用int数组0代表未访问±1代表两种颜色最省事。2.3 BFS版本与递归栈的取舍DFS染色在链状图、深度极大的图上可能会爆栈。虽然CSP-S的Linux环境栈空间通常有8MB递归10⁵层一般问题不大但如果你心里没底或者本地Windows栈小就直接写BFS版本bool bfsCheck(int start) { queueint q; q.push(start); color[start] 1; while (!q.empty()) { int u q.front(); q.pop(); for (int v : G[u]) { if (color[v] color[u]) return false; if (color[v] 0) { color[v] -color[u]; q.push(v); } } } return true; }BFS版本的好处是天然没有递归深度问题而且用层数理解“同层边会导致奇环”更直观。我个人的习惯是除非DFS会明显爆栈否则优先DFS因为代码短、写起来快考场上少敲几行就少几个出错机会。3. 匈牙利算法求最大匹配背模板之前先懂增广路3.1 匹配、最大匹配、增广路到底在说什么先明确定义二分图里匹配是边的一个子集任意两条匹配边没有公共端点。最大匹配就是包含边数最多的匹配。匈牙利算法的核心是“增广路”。什么叫增广路从一个未匹配的左部点出发走一条路径路径上的边交替出现“非匹配边、匹配边、非匹配边……”最后到达一个未匹配的右部点。这条路径就叫增广路。为什么叫“增广”因为只要把路径上的匹配边和非匹配边互换——匹配边变成非匹配非匹配边变成匹配——匹配数就会增加1。打个比方你现在有一对舞伴来了一个新男生想加入他先邀请一个女生这个女生现在的舞伴再去邀请另一个女生……如果最终能拉进来一个空着的女生那么这条“连锁反应链”上的配对关系全部更新一次总配对数就多了一。匈牙利算法的思想就是不断从左部未匹配点出发找增广路找到一条就让匹配数加一直到找不到为止。这里有个关键定理Berge定理当前匹配是最大匹配当且仅当不存在增广路。这个定理是整套算法的理论基石。3.2 完整模板左侧DFS 右侧match 每轮vis最常见的写法是DFS版左侧每个点尝试增广一次右侧用vis数组保证同一轮尝试不重复访问同一个右部点const int MAXN 505; vectorint G[MAXN]; // 左部点指向右部点的边 int match[MAXN]; // match[v]表示右部点v当前匹配的左部点0表示未匹配 bool vis[MAXN]; // 当前这轮DFS右部点是否被访问过 bool dfs(int u) { for (int v : G[u]) { if (vis[v]) continue; vis[v] true; if (match[v] 0 || dfs(match[v])) { match[v] u; return true; } } return false; } int hungarian(int leftCount) { int res 0; memset(match, 0, sizeof(match)); for (int i 1; i leftCount; i) { memset(vis, 0, sizeof(vis)); if (dfs(i)) res; } return res; }这里有一个所有新手都会困惑的点为什么每轮都要清空vis因为vis的作用是“当前这条增广路尝试”里某个右部点已经被访问过不能再被重复递归否则会形成死循环。但它不负责记忆“之前轮次的访问结果”每一轮都是全新的起点、全新的尝试所以必须在每次调用dfs之前清空。如果忘了清空前面的失败尝试会把后续轮次的右部点全部标记为“已访问”导致大量增广路找不到匹配数偏小。还有一个容易写错的地方dfs递归里如果match[v]存在要递归的是dfs(match[v])这里的match[v]是左部点编号。也就是说我让当前已经匹配了右部点v的那个左部点再去另找新的右部点。这个“让位”的逻辑正是增广路的本质。3.3 复杂度真相与Hopcroft-Karp的取舍匈牙利算法的理论复杂度是O(VE)其中V是左部点数量E是边数。在CSP-S的数据范围里两侧点数500左右、边数几万这个复杂度完全没问题。实际跑起来常数很小因为DFS搜到增广路就返回不会真把整张图搜满。但要注意如果点数到10⁴、边数到10⁵O(VE)就会超时。这时候可以上Hopcroft-Karp算法HK算法它通过BFS分层 多路增广把复杂度降到O(E√V)。HK算法在CSP-S里考得极少但如果你想冲省队或者准备NOI建议掌握。我的建议是先把DFS匈牙利写到闭眼都能敲出来的程度再去碰HK否则容易两头都不扎实。4. 三大经典结论最小点覆盖、最大独立集、最小路径覆盖4.1 König定理是怎么来的二分图里有一条非常漂亮的定理最小点覆盖 最大匹配。点覆盖的意思是选最少的点让每一条边至少有一个端点被选中。证明思路不复杂但构造性很强。从左部所有未匹配点出发沿着“非匹配边→匹配边→非匹配边→……”的交替路径走标记访问到的点。然后取左部未被访问的点加上右部被访问到的点得到的点集就是一个点覆盖大小恰好等于最大匹配数。反过来最大匹配里的边一定是两两不共端点的覆盖所有边至少要每一条匹配边选一个点所以最小点覆盖不可能小于最大匹配数。这个定理的实践意义在于它把“选点覆盖边”这个看着像贪心的问题转化成了“求最大匹配”而最大匹配我们已经会求了。4.2 三大结论怎么落地判别特征和用例要解决的问题二分图上的结论题目特征选最少的点覆盖所有边最小点覆盖 最大匹配“每条限制至少有一端被选中”选最多的点使任意两点不相连最大独立集 总点数 - 最大匹配“任意两个选中对象之间无冲突”用最少的路径覆盖DAG所有顶点最小路径覆盖 原图顶点数 - 拆点后最大匹配“每个点走一次尽量把点串成链”这里要特别提醒这三个结论只对二分图严格成立。很多同学记住了“最大独立集 n - 最大匹配”但一遇到普通图也这么套必错。先判断这个图是不是二分图再决定能不能用这套公式。最大独立集的结论可以用补集理解点覆盖的补集就是独立集。因为一个点是“覆盖所有边”的集合它的补集里就不会有任何一条边的两个端点同时出现否则这条边没被覆盖。所以最大独立集和最小点覆盖加起来等于总点数。4.3 例题棋盘骨牌覆盖为什么是二分图这个例子特别能说明建模过程。棋盘上有一些格子被挖掉用1×2的骨牌覆盖剩下的格子问最多能放多少块骨牌。第一步把棋盘上的格子按(ij)的奇偶性染色。下标(i,j)和为偶数的格子归入左部和为奇数的格子归入右部。第二步任意相邻格子的(ij)奇偶性必然相反所以相邻关系天然是“左部到右部”的边集合内部没有边正好是二分图。第三步一块1×2骨牌恰好覆盖一条边占掉两个邻接的不同色格子。所以“最多放多少骨牌”就是“最多选多少条互不共端点的边”这就是最大匹配。第四步求最大匹配答案就是骨牌数量。这种黑白染色建模在棋盘问题上特别常用不只是骨牌覆盖还有马走日互不攻击、相邻格子冲突、黑白棋盘染色等套路都一个样棋盘格子本身分成两类约束关系变成两集合之间的边。5. 建模实战从“看不出二分图”到“一眼二分图”5.1 冲突关系模型二分答案 染色判定最经典的例子是NOIP2010提高组的关押罪犯。题意简化版有n个罪犯、两个监狱罪犯之间有怨气值你要把所有人分进两个监狱使监狱内部任意两人的怨气值最大值最小。这题的建模思路是倒着想的二分答案mid问题变成“能否让所有怨气值大于mid的罪犯对都被分到不同监狱”。把怨气值大于mid的点对连边连出来的图如果能够二染色就说明可以分成两个集合且这两个集合对应两个监狱。于是判定就变成了对怨气值大于mid的边构成的图做染色法。“两个监狱”天然是二分图里的两个集合所以只要理解了二分图的本质这题就是一个“二分答案 染色法判定”的组合拳。复杂度O(logW × (n m))W是怨气值上限完全能过。这类冲突模型的识别特征很明确题目里有“两类容器”“两种颜色”“两个组”要求把所有对象分配进去同时对象之间有冲突关系问的是冲突最小化或是否可行。看到这种题第一反应就应该是二分答案 染色判定。5.2 两集合匹配模型行和列、男生和女生、任务和机器假设题目是这样有一个n×n的棋盘某些格子可以放棋子要求每行每列最多放一个问最多能放多少个。这个模型更直接左部集合行1到n右部集合列1到n如果第i行第j列的格子可以放棋子就连接左部点i和右部点j每行每列最多选一个等价于匹配中每个左部点和右部点最多被一条边覆盖所以最大可放棋子数 最大匹配数。这类模型的识别特征是“两类对象之间的一一匹配限制”。课程与学生、任务与机器、行与列、员工与班次全是同一个套路。比写代码更重要的是你能不能在读题时主动把“行”和“列”提取成两个集合。我见过很多同学在这里犯懒非要在脑子里面模拟放棋子的过程然后写一个带回溯的搜索。搜索当然能过小数据但题目稍微给到n100就直接超时。正确做法是识别模型、建图、套模板三步走别自己去模拟匹配过程。5.3 覆盖/独立集模型验证二分图后再套公式再看一个稍微综合的例子有n个人、m对朋友关系。要求选一支队伍任意两个队员不能是朋友关系问最多选多少人。拿到这题先别急着写代码。第一步是判断朋友关系图是不是二分图比如题目如果额外给了“所有人分成男生组和女生组朋友关系只在异性之间”那它天然是二分图。如果没有这个条件那大概率不是在考二分图最大独立集而是别的算法。确认是二分图之后答案就是n - 最大匹配。原因就是最大独立集公式。这题想提醒你的仍然是那句话三大结论的前提是二分图这个前提丢了公式没有任何意义。我做这类题的顺序通常是这样先画图把“谁和谁有冲突/匹配关系”用边表示出来再染色验证二分性最后再决定是求匹配、最小点覆盖、最大独立集还是配合二分答案做判定。图一画出来很多隐藏条件就藏不住了。6. 考场上识别二分图的思维链以及我踩过的几个老坑6.1 拿到题后三分钟内的提问顺序我自己做题和带学生都习惯固定在读题阶段问自己下面几个问题顺序很重要题目里有没有明显的“两类对象”行和列、男生和女生、两个监狱、黑色和白色这些词一出现优先怀疑二分图。约束条件是不是“一一对应”的匹配关系每个任务只能分配给一个人、每行最多选一个这种措辞几乎就是在说匹配。要求求的是“是否可行”还是“最大/最小值”可行性的往往和染色判定有关最大/最小值的往往和匹配数有关。数据范围支持什么复杂度n≤500直接想匈牙利n≤10⁵猜测配合二分答案。能不能把“冲突”翻译成边“和A冲突”的B在二分图里就是一条边。建出来的图是不是二分图如果不是看看是否要二分某个答案之后再建图。这套顺序看着死板但考场上特别能救命。尤其是第6条很多题目要二分答案之后图才是二分图想通这一点整道题就从“完全没思路”变成“模板题”。6.2 模板使用的四个注意事项这里每一条都是我自己或学生实际踩过的坑第一数组下标和大小。CSP-S的题普遍从1开始编号数组就开成MAXN5不要用0开始的习惯硬套否则最后一刻调bug心态容易崩。第二染色法必须遍历所有连通分量。只从一个起点染色遇到不连通图会误判。第三匈牙利每一轮DFS开始前必须清空vis。忘了清空匹配数会出错而且这种错很难一眼看出来因为结果不是0而是一个偏小的错误值。第四match数组的方向要固定。我习惯用match[v]表示“右部点v匹配的左部点”对应代码里递归dfs(match[v])。如果你习惯反着记也可以但一定要在注释里写清楚不然写了一半自己都分不清。6.3 给不同水平选手的备赛建议如果是刚开始学建议按这个顺序刷题先用洛谷P1330封锁阳光大学把染色法理解透这题还顺带考了连通分量和计数再刷P3386二分图最大匹配模板把匈牙利算法写得滚瓜烂熟然后上P1525关押罪犯体会二分答案染色判定的组合最后做P1129矩阵游戏和P2764最小路径覆盖问题练建模。如果已经有基础更重要的不是多刷题而是训练“读题时主动建图”的习惯。我建议每次拿到新题先不看题解强制自己在草稿纸上写出左部集合是什么、右部集合是什么、边代表什么关系、最后套哪个结论。哪怕想了十分钟发现不是二分图也比直接看题解有价值。如果你还在准备初赛把历年CSP-S初赛里和图论、二分图相关的选择题刷一遍就够。初赛不考写代码考的是概念和复杂度分析理解了染色法的原理和复杂度那几道题基本稳拿。最后再说两句二分图这块内容说难不难说简单也不简单。它的难不在算法本身而在“看出来”。我带集训队最深的体会是一个学生能不能过提高组的图论题很多时候不取决于他会多少算法而取决于他能不能在陌生的题干里认出熟悉的模型。所以这篇文章虽然给了模板但我更希望你带走的是那套建模思路找两类对象翻译成边验证二分性再套结论。做完这些剩下的就是把模板稳稳地默写到答题卡上。
