信奥赛C++二分图算法：从基础到实战应用

1. 信奥赛C++提高组中的二分图算法精要

信奥赛C++提高组的二分图题目往往考察选手对图论基础概念的掌握程度和算法实现能力。二分图（Bipartite Graph）是指顶点集V可以分割为两个互不相交的子集，并且图中每条边所关联的两个顶点分别属于这两个不同的子集。这个看似简单的定义在实际解题中却蕴含着丰富的应用场景和解题技巧。

在CSP-S级别的竞赛中，二分图相关题目通常会以以下形式出现：

• 判定题：判断给定图是否为二分图
• 匹配问题：求二分图的最大匹配
• 着色问题：使用两种颜色对顶点进行着色
• 建模题：将实际问题抽象为二分图模型

提示：二分图判定是许多复杂图论问题的基础步骤，务必熟练掌握DFS/BFS着色法和并查集两种判定方法。

1.1 二分图的基本性质与判定

二分图的判定通常采用着色法，这是信奥赛中最常考察的基础算法之一。其核心思想是通过遍历（DFS或BFS）为图中的顶点交替着色，如果在着色过程中发现相邻顶点颜色相同，则判定不是二分图。

// DFS实现二分图判定 bool isBipartite(vector<vector<int>>& graph) { int n = graph.size(); vector<int> color(n, 0); // 0未着色，1和2表示两种颜色 for (int i = 0; i < n; ++i) { if (color[i] == 0) { stack<int> stk; stk.push(i); color[i] = 1; while (!stk.empty()) { int node = stk.top(); stk.pop(); for (int neighbor : graph[node]) { if (color[neighbor] == 0) { color[neighbor] = color[node] == 1 ? 2 : 1; stk.push(neighbor); } else if (color[neighbor] == color[node]) { return false; } } } } } return true; }

在实际竞赛中，需要注意几个关键点：

1. 图可能不连通，需要检查每个连通分量
2. 着色只需要两种颜色，复杂度为O(V+E)
3. 邻接表存储时要注意空间复杂度

1.2 二分图的最大匹配问题

匈牙利算法是解决二分图最大匹配问题的经典算法，其时间复杂度为O(VE)。虽然理论上不是最优的，但在信奥赛的数据规模下（通常V≤500）完全够用。

// 匈牙利算法实现 bool bpm(vector<vector<bool>>& bpGraph, int u, vector<bool>& seen, vector<int>& matchR) { for (int v = 0; v < bpGraph[0].size(); v++) { if (bpGraph[u][v] && !seen[v]) { seen[v] = true; if (matchR[v] < 0 || bpm(bpGraph, matchR[v], seen, matchR)) { matchR[v] = u; return true; } } } return false; } int maxBPM(vector<vector<bool>>& bpGraph) { vector<int> matchR(bpGraph[0].size(), -1); int result = 0; for (int u = 0; u < bpGraph.size(); u++) { vector<bool> seen(bpGraph[0].size(), false); if (bpm(bpGraph, u, seen, matchR)) result++; } return result; }

竞赛中常见的优化技巧包括：

1. 使用邻接表而非邻接矩阵存储稀疏图
2. 添加预处理步骤快速排除明显不匹配的情况
3. 对顶点按度数排序，优先处理度数小的顶点

2. 二分图在信奥赛中的典型应用场景

2.1 任务分配问题建模

这是二分图最经典的应用场景。例如有n个任务和m个人员，每个人员能完成某些特定任务，要求找出最多能完成的任务数量。这类问题可以直接建模为二分图匹配：

• 左部顶点表示人员
• 右部顶点表示任务
• 边表示人员能完成的任务

// 任务分配问题示例 vector<vector<bool>> buildGraph(const vector<pair<int, int>>& abilities) { int n = getMaxPerson(abilities); // 获取最大人员编号 int m = getMaxTask(abilities); // 获取最大任务编号 vector<vector<bool>> graph(n, vector<bool>(m, false)); for (auto& ab : abilities) { int person = ab.first; int task = ab.second; graph[person][task] = true; } return graph; }

2.2 棋盘覆盖问题

许多棋盘覆盖问题可以转化为二分图模型。例如在8x8棋盘上放置车，要求不互相攻击。可以将棋盘的行和列分别作为二分图的两部分顶点，每个方格对应一条边。

// 棋盘覆盖问题示例 vector<vector<bool>> buildChessGraph(const vector<string>& chessboard) { int n = chessboard.size(); int m = chessboard[0].size(); vector<vector<bool>> graph(n, vector<bool>(m, false)); for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (chessboard[i][j] == '.') { // 可放置位置 graph[i][j] = true; } } } return graph; }

2.3 稳定婚姻问题

这是二分图的另一个经典应用，可以使用Gale-Shapley算法解决。虽然不常直接出现在竞赛中，但理解其原理有助于解决其他匹配问题。

3. 二分图进阶算法与优化

3.1 二分图的最小顶点覆盖

根据König定理，二分图中最小顶点覆盖数等于最大匹配数。这为解决某些覆盖问题提供了高效思路。

// 基于匈牙利算法找最小顶点覆盖 vector<int> minVertexCover(vector<vector<bool>>& bpGraph) { vector<int> matchR(bpGraph[0].size(), -1); // 先求最大匹配 // ...匈牙利算法代码同上... // 然后根据匹配找覆盖 vector<bool> visited(bpGraph.size(), false); vector<int> cover; // 实现细节略... return cover; }

3.2 二分图的最大独立集

在二分图中，最大独立集的大小等于顶点数减去最小顶点覆盖数。这个性质在某些组合优化问题中非常有用。

3.3 带权二分图的最佳匹配

对于有权二分图，可以使用KM算法（Kuhn-Munkres算法）求解最佳完美匹配。虽然CSP-S中较少出现，但在NOI及以上级别比赛中可能涉及。

// KM算法框架 class KM { vector<vector<int>> graph; vector<int> lx, ly; // 顶标 vector<bool> visx, visy; vector<int> match; int n; public: KM(vector<vector<int>> g) : graph(g) { n = graph.size(); // 初始化代码... } bool find(int x) { // 寻找增广路 } int solve() { // KM算法主过程 } };

4. 竞赛中的常见错误与调试技巧

4.1 二分图建模错误

常见错误包括：

1. 错误识别二分图的两部分顶点
2. 忽略图的连通性导致判定错误
3. 顶点编号处理不当（特别是0-based和1-based混用）

调试建议：

• 打印图的邻接表表示
• 可视化小规模测试用例
• 检查顶点数量和边数量是否匹配预期

4.2 匈牙利算法实现陷阱

常见问题：

1. 忘记重置visited数组
2. 递归实现栈溢出（对大规模图应用非递归版本）
3. 匹配数组初始化错误

// 正确的visited数组重置 for (int u = 0; u < n; u++) { vector<bool> visited(m, false); // 每次必须重新初始化 if (dfs(u, visited, match)) { result++; } }

4.3 性能优化技巧

对于大规模数据：

1. 使用邻接表而非邻接矩阵
2. 添加贪心初始匹配
3. 使用Hopcroft-Karp算法（O(E√V)）替代匈牙利算法

// Hopcroft-Karp算法框架 class HopcroftKarp { vector<vector<int>> adj; vector<int> pairU, pairV, dist; int nil, U, V; bool bfs() { // 分层 } bool dfs(int u) { // 寻找增广路 } public: int maxMatching() { // 算法主过程 } };

5. 典型题目分析与实战演练

5.1 CSP-S真题解析：2021年二分图应用题

题目大意：给定一个n×m的网格，某些格子有障碍物。要求放置最少数量的监控摄像头，每个摄像头可以监视同一行和同一列的所有格子（除非被障碍物阻挡）。求最少需要多少个摄像头。

解题思路：

1. 将每行无障碍的连续区间视为左部顶点
2. 将每列无障碍的连续区间视为右部顶点
3. 每个可放置摄像头的位置对应一条边
4. 问题转化为求二分图的最小顶点覆盖

// 建图关键代码 vector<vector<bool>> buildGraph(const vector<string>& grid) { // 提取行连续区间 vector<Interval> rowIntervals = extractRowIntervals(grid); // 提取列连续区间 vector<Interval> colIntervals = extractColIntervals(grid); vector<vector<bool>> graph(rowIntervals.size(), vector<bool>(colIntervals.size(), false)); for (int i = 0; i < grid.size(); ++i) { for (int j = 0; j < grid[0].size(); ++j) { if (grid[i][j] == '.') { int ri = findRowInterval(rowIntervals, i, j); int ci = findColInterval(colIntervals, i, j); graph[ri][ci] = true; } } } return graph; }

5.2 NOIP提高组模拟题：团队协作匹配

题目描述：有n个学生和m个项目，每个学生有若干擅长的技能，每个项目需要特定的技能组合。问最多能同时开展多少个项目，每个项目由一个学生负责，且学生必须拥有项目所需的所有技能。

解题步骤：

1. 对每个项目，找出拥有所有必需技能的学生
2. 建立学生到项目的二分图
3. 求最大匹配

vector<vector<bool>> buildGraph(const vector<Student>& students, const vector<Project>& projects) { vector<vector<bool>> graph(students.size(), vector<bool>(projects.size(), false)); for (int s = 0; s < students.size(); ++s) { for (int p = 0; p < projects.size(); ++p) { bool qualified = true; for (int skill : projects[p].requiredSkills) { if (students[s].skills.find(skill) == students[s].skills.end()) { qualified = false; break; } } graph[s][p] = qualified; } } return graph; }

5.3 在线评测平台高频题目训练

推荐练习题目：

1. 洛谷P3386 【模板】二分图最大匹配
2. POJ 3041 Asteroids（最小顶点覆盖经典题）
3. HDU 1045 Fire Net（棋盘问题建模）
4. CodeForces 489B BerSU Ball（简单匹配问题）
5. UVA 1194 Machine Schedule（最小顶点覆盖应用）

对于每道题目，建议：

1. 先独立尝试建模和解题
2. 对比标准解法分析差异
3. 总结建模技巧和算法选择依据
4. 记录解题时间和错误点

6. 二分图算法的扩展应用

6.1 网络流中的二分图应用

二分图问题可以转化为网络流问题求解。建立超级源点和超级汇点后，使用Dinic等算法可能获得更好的时间复杂度。

// 二分图匹配转最大流 int bipartiteToFlow(vector<vector<int>>& graph) { int n = graph.size(); int m = 0; for (auto& edges : graph) { for (int v : edges) { m = max(m, v); } } m++; // 假设右部顶点编号从0开始 FlowNetwork fn(n + m + 2); int source = n + m; int sink = n + m + 1; // 添加源点到左部顶点的边 for (int u = 0; u < n; ++u) { fn.addEdge(source, u, 1); } // 添加原始二分图的边 for (int u = 0; u < n; ++u) { for (int v : graph[u]) { fn.addEdge(u, n + v, 1); } } // 添加右部顶点到汇点的边 for (int v = 0; v < m; ++v) { fn.addEdge(n + v, sink, 1); } return fn.maxFlow(source, sink); }

6.2 二分图在树结构中的应用

许多树结构问题可以转化为二分图问题。例如，树的顶点可以被二着色，本身就是二分图。这个性质在解决树上的匹配、覆盖问题时非常有用。

6.3 三分图及其他扩展

虽然竞赛中较少出现，但了解三分图等概念有助于拓展解题思路。三分图是指顶点可以划分为三个互不相交的集合，且边只在不同集合顶点之间的图。

7. 竞赛备战建议与学习资源

7.1 系统化学习路径

1. 基础阶段：

   • 掌握图的基本表示方法（邻接矩阵、邻接表）
   • 理解二分图定义和判定方法
   • 实现简单匈牙利算法

2. 进阶阶段：

   • 学习König定理及其证明
   • 掌握Hopcroft-Karp算法
   • 理解网络流与二分图的关系

3. 应用阶段：

   • 练习典型建模问题（任务分配、棋盘覆盖等）
   • 参加虚拟比赛积累实战经验
   • 分析历年真题解题思路

7.2 推荐学习资源

书籍：

• 《算法竞赛入门经典》（刘汝佳）图论章节
• 《算法导论》二分图相关章节
• 《挑战程序设计竞赛》二分图专题

在线资源：

• OI Wiki二分图专题
• Codeforces教育板块图论教程
• 洛谷官方题解和用户分享

7.3 训练计划建议

为期8周的二分图专项训练计划：

7.4 调试与优化实战技巧

1. 小数据测试法：

   • 手工构造小规模测试用例
   • 验证算法每个步骤的正确性
   • 特别检查边界情况（空图、完全图等）

2. 对拍验证：

   • 编写朴素算法作为验证基准
   • 生成随机测试数据比较结果
   • 使用脚本自动化测试过程

#!/bin/bash g++ -std=c++11 main.cpp -o main g++ -std=c++11 brute.cpp -o brute g++ -std=c++11 gen.cpp -o gen for ((i=1;i<=1000;i++)); do ./gen > input.txt ./main < input.txt > output.txt ./brute < input.txt > answer.txt if diff output.txt answer.txt; then echo "Test $i: PASSED" else echo "Test $i: FAILED" break fi done

3. 性能分析方法：
   • 使用clock()函数测量关键代码段耗时
   • 分析算法复杂度是否符合预期
   • 针对瓶颈进行优化（如改用更快的输入方法）

#include <ctime> void testPerformance() { clock_t start = clock(); // 待测试的算法代码 int result = maxBPM(graph); clock_t end = clock(); double duration = (double)(end - start) / CLOCKS_PER_SEC; cout << "Result: " << result << ", Time: " << duration << "s" << endl; }

二分图作为图论中的重要概念，在信奥赛C++提高组竞赛中占据着关键地位。通过系统学习和大量练习，掌握二分图的各种算法和应用场景，不仅能解决直接的二分图问题，还能培养将复杂问题抽象为图论模型的思维能力。建议从基础判定算法开始，逐步过渡到匹配、覆盖等高级应用，最后通过真题训练提升实战能力。记住，在竞赛中正确建模往往比算法实现更重要，因此要多积累不同场景下的建模经验。