企业官网建设流程全解析

带集训队这几年，我发现一个很有意思的现象：很多学生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(n+m)或O(VE)级别的算法，而不是DFS爆搜。遇到这类范围，思路往图论模型上靠，成功率会高很多。

2. 染色法判定二分图：模板背后的三条逻辑链

2.1 为什么“无奇环”是判定的核心

染色法的思路很朴素：随便选一个点染成黑色，它的所有邻居染成白色，邻居的邻居染成黑色……如果过程中发现一条边的两个端点已经被染成了同一种颜色，说明矛盾，这个图不是二分图。

这个算法背后的逻辑链值得想明白：

• 如果图是二分图，从任一顶点出发，它所在集合就确定了，同一集合内的点必须同色，跨集合的点必须异色。所以染色的结果是唯一的（每个连通分量内只有两种互斥方案）。
• 如果染色失败，说明存在一条边两端同色。沿着DFS树看，这条边会和一个树上的路径拼成一个环。
• 树上的相邻节点颜色必然交替，一条路径如果从某个颜色出发，回到同色节点，需要的步数是偶数；再加上这条同色边，环的总长度就是奇数。
• 所以染色失败 = 存在奇环 = 不是二分图。

反过来，无奇环的图一定能染色成功，这就是等价性。理解了这层，你就不会在“到底要不要处理重边”“孤立点怎么办”这种细节上空耗：重边不影响二染色，孤立点随便染。

2.2 DFS模板和两个“看起来对但必错”的写法

直接上一份我平时给集训队用的模板：

#include <bits/stdc++.h> using namespace std; const int MAXN = 100005; vector<int> 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) { queue<int> 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; vector<int> 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 三大结论怎么落地：判别特征和用例

这里要特别提醒：这三个结论只对二分图严格成立。很多同学记住了“最大独立集 = n - 最大匹配”，但一遇到普通图也这么套，必错。先判断这个图是不是二分图，再决定能不能用这套公式。

最大独立集的结论可以用补集理解：点覆盖的补集就是独立集。因为一个点是“覆盖所有边”的集合，它的补集里就不会有任何一条边的两个端点同时出现，否则这条边没被覆盖。所以最大独立集和最小点覆盖加起来等于总点数。

4.3 例题：棋盘骨牌覆盖为什么是二分图

这个例子特别能说明建模过程。棋盘上有一些格子被挖掉，用1×2的骨牌覆盖剩下的格子，问最多能放多少块骨牌。

第一步：把棋盘上的格子按(i+j)的奇偶性染色。下标(i,j)和为偶数的格子归入左部，和为奇数的格子归入右部。

第二步：任意相邻格子的(i+j)奇偶性必然相反，所以相邻关系天然是“左部到右部”的边，集合内部没有边，正好是二分图。

第三步：一块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；
• 每行每列最多选一个，等价于匹配中每个左部点和右部点最多被一条边覆盖；
• 所以最大可放棋子数 = 最大匹配数。

这类模型的识别特征是“两类对象之间的一一匹配限制”。课程与学生、任务与机器、行与列、员工与班次，全是同一个套路。比写代码更重要的是你能不能在读题时主动把“行”和“列”提取成两个集合。

我见过很多同学在这里犯懒，非要在脑子里面模拟放棋子的过程，然后写一个带回溯的搜索。搜索当然能过小数据，但题目稍微给到n=100，就直接超时。正确做法是：识别模型、建图、套模板，三步走，别自己去模拟匹配过程。

5.3 覆盖/独立集模型：验证二分图后再套公式

再看一个稍微综合的例子：有n个人、m对朋友关系。要求选一支队伍，任意两个队员不能是朋友关系，问最多选多少人。

拿到这题，先别急着写代码。第一步是判断朋友关系图是不是二分图，比如题目如果额外给了“所有人分成男生组和女生组，朋友关系只在异性之间”，那它天然是二分图。如果没有这个条件，那大概率不是在考二分图最大独立集，而是别的算法。

确认是二分图之后，答案就是n - 最大匹配。原因就是最大独立集公式。这题想提醒你的仍然是那句话：三大结论的前提是二分图，这个前提丢了，公式没有任何意义。

我做这类题的顺序通常是这样：先画图，把“谁和谁有冲突/匹配关系”用边表示出来；再染色验证二分性；最后再决定是求匹配、最小点覆盖、最大独立集，还是配合二分答案做判定。图一画出来，很多隐藏条件就藏不住了。

6. 考场上识别二分图的思维链，以及我踩过的几个老坑

6.1 拿到题后三分钟内的提问顺序

我自己做题和带学生，都习惯固定在读题阶段问自己下面几个问题，顺序很重要：

1. 题目里有没有明显的“两类对象”？行和列、男生和女生、两个监狱、黑色和白色，这些词一出现，优先怀疑二分图。
2. 约束条件是不是“一一对应”的匹配关系？每个任务只能分配给一个人、每行最多选一个，这种措辞几乎就是在说匹配。
3. 要求求的是“是否可行”还是“最大/最小值”？可行性的往往和染色判定有关，最大/最小值的往往和匹配数有关。
4. 数据范围支持什么复杂度？n≤500直接想匈牙利，n≤10⁵猜测配合二分答案。
5. 能不能把“冲突”翻译成边？“和A冲突”的B，在二分图里就是一条边。
6. 建出来的图是不是二分图？如果不是，看看是否要二分某个答案之后再建图。

这套顺序看着死板，但考场上特别能救命。尤其是第6条，很多题目要二分答案之后图才是二分图，想通这一点，整道题就从“完全没思路”变成“模板题”。

6.2 模板使用的四个注意事项

这里每一条都是我自己或学生实际踩过的坑：

第一，数组下标和大小。CSP-S的题普遍从1开始编号，数组就开成MAXN+5，不要用0开始的习惯硬套，否则最后一刻调bug心态容易崩。

第二，染色法必须遍历所有连通分量。只从一个起点染色，遇到不连通图会误判。

第三，匈牙利每一轮DFS开始前必须清空vis。忘了清空，匹配数会出错，而且这种错很难一眼看出来，因为结果不是0，而是一个偏小的错误值。

第四，match数组的方向要固定。我习惯用match[v]表示“右部点v匹配的左部点”，对应代码里递归dfs(match[v])。如果你习惯反着记，也可以，但一定要在注释里写清楚，不然写了一半自己都分不清。

6.3 给不同水平选手的备赛建议

如果是刚开始学，建议按这个顺序刷题：先用洛谷P1330封锁阳光大学把染色法理解透，这题还顺带考了连通分量和计数；再刷P3386二分图最大匹配模板，把匈牙利算法写得滚瓜烂熟；然后上P1525关押罪犯，体会二分答案+染色判定的组合；最后做P1129矩阵游戏和P2764最小路径覆盖问题，练建模。

如果已经有基础，更重要的不是多刷题，而是训练“读题时主动建图”的习惯。我建议每次拿到新题，先不看题解，强制自己在草稿纸上写出：左部集合是什么、右部集合是什么、边代表什么关系、最后套哪个结论。哪怕想了十分钟发现不是二分图，也比直接看题解有价值。

如果你还在准备初赛，把历年CSP-S初赛里和图论、二分图相关的选择题刷一遍就够。初赛不考写代码，考的是概念和复杂度分析，理解了染色法的原理和复杂度，那几道题基本稳拿。

最后再说两句

二分图这块内容，说难不难，说简单也不简单。它的难不在算法本身，而在“看出来”。我带集训队最深的体会是：一个学生能不能过提高组的图论题，很多时候不取决于他会多少算法，而取决于他能不能在陌生的题干里认出熟悉的模型。所以这篇文章虽然给了模板，但我更希望你带走的是那套建模思路：找两类对象，翻译成边，验证二分性，再套结论。

做完这些，剩下的就是把模板稳稳地默写到答题卡上。