信奥赛C++提高组二分图算法精解与应用

1. 二分图在信奥赛C++提高组中的核心地位

信奥赛C++提高组（CSP-S）的题目中，二分图是一个高频出现的核心考点。作为图论中的重要概念，二分图能够将复杂问题转化为清晰的数学模型，特别适合解决匹配、覆盖等经典问题。在实际比赛中，选手需要快速识别题目中的二分图特征，并运用相应算法高效解题。

二分图判定是基础中的基础。一个无向图G=(V,E)若能将其顶点集V划分为两个不相交的子集V1和V2，使得图中每条边的两个端点分别属于这两个子集，则称G为二分图。在实际编程实现中，通常使用染色法进行判定：

bool isBipartite(vector<vector<int>>& graph) { int n = graph.size(); vector<int> color(n, -1); queue<int> q; for (int i = 0; i < n; ++i) { if (color[i] == -1) { q.push(i); color[i] = 0; while (!q.empty()) { int node = q.front(); q.pop(); for (int neighbor : graph[node]) { if (color[neighbor] == -1) { color[neighbor] = color[node] ^ 1; q.push(neighbor); } else if (color[neighbor] == color[node]) { return false; } } } } } return true; }

注意：染色法使用BFS或DFS均可，但要注意处理非连通图的情况，需要检查每个连通分量是否都是二分图。

2. 二分图匹配算法精解

2.1 匈牙利算法实现细节

匈牙利算法是解决二分图最大匹配问题的经典算法，时间复杂度为O(VE)。在竞赛中，掌握其优化版本至关重要：

vector<int> match; // 记录匹配结果 vector<bool> used; // 记录访问标记 bool dfs(int v, const vector<vector<int>>& graph) { for (int u : graph[v]) { if (!used[u]) { used[u] = true; if (match[u] == -1 || dfs(match[u], graph)) { match[u] = v; return true; } } } return false; } int hungarian(const vector<vector<int>>& graph, int n, int m) { match.assign(m, -1); int result = 0; for (int v = 0; v < n; ++v) { used.assign(m, false); if (dfs(v, graph)) ++result; } return result; }

实际比赛中常见的优化技巧包括：

1. 使用邻接表而非邻接矩阵存储图结构
2. 对顶点按度数排序，先处理度数小的顶点
3. 使用时间戳优化used数组的初始化

2.2 Hopcroft-Karp算法的高效实现

对于大规模二分图匹配问题，Hopcroft-Karp算法（时间复杂度O(E√V)）更为高效：

const int NIL = -1; const int INF = INT_MAX; vector<int> pairU, pairV, dist; vector<vector<int>> adj; bool bfs(int nu, int nv) { queue<int> q; for (int u = 0; u < nu; ++u) { if (pairU[u] == NIL) { dist[u] = 0; q.push(u); } else { dist[u] = INF; } } dist[NIL] = INF; while (!q.empty()) { int u = q.front(); q.pop(); if (dist[u] < dist[NIL]) { for (int v : adj[u]) { if (dist[pairV[v]] == INF) { dist[pairV[v]] = dist[u] + 1; q.push(pairV[v]); } } } } return dist[NIL] != INF; } bool dfs(int u) { if (u != NIL) { for (int v : adj[u]) { if (dist[pairV[v]] == dist[u] + 1) { if (dfs(pairV[v])) { pairU[u] = v; pairV[v] = u; return true; } } } dist[u] = INF; return false; } return true; } int hopcroftKarp(int nu, int nv) { pairU.assign(nu, NIL); pairV.assign(nv, NIL); dist.resize(nu + 1); int matching = 0; while (bfs(nu, nv)) { for (int u = 0; u < nu; ++u) { if (pairU[u] == NIL && dfs(u)) { ++matching; } } } return matching; }

3. 二分图在竞赛中的典型应用

3.1 最小点覆盖与König定理

König定理指出：在二分图中，最大匹配数等于最小点覆盖数。这为解决许多覆盖类问题提供了理论依据。典型应用场景包括：

1. 任务分配问题：将任务和人员建模为二分图的两部
2. 棋盘覆盖问题：将棋盘建模为二分图，利用行列关系
3. 资源调度问题：将资源和需求抽象为二分图

实现最小点覆盖的算法步骤：

1. 找到最大匹配M
2. 从左侧未匹配点出发进行DFS/BFS标记可达点
3. 最小点覆盖集 = 左侧未标记点 ∪ 右侧已标记点

3.2 最大独立集与团问题

在二分图中，最大独立集的大小等于顶点数减去最大匹配数。这一性质常用于解决：

1. 冲突避免问题：如课程安排、活动调度
2. 稳定集问题：寻找图中无直接边连接的最大顶点集
3. 反图应用：将原问题的补图建模为二分图

vector<int> findMaxIndependentSet(const vector<vector<int>>& graph, int n, int m) { int matching = hungarian(graph, n, m); vector<bool> visited(n + m, false); // 实现标记过程... vector<int> result; // 根据标记结果收集独立集顶点 return result; }

4. 竞赛中的高级应用与变形

4.1 带权二分图与KM算法

对于带权二分图的最大权匹配问题，Kuhn-Munkres（KM）算法是标准解法。其核心思想是通过顶标调整寻找完美匹配：

vector<int> u, v, p, way; vector<vector<int>> matrix; int hungarian(int n, int m) { u.assign(n + 1, 0); v.assign(m + 1, 0); p.assign(m + 1, 0); way.assign(m + 1, 0); for (int i = 1; i <= n; ++i) { p[0] = i; int j0 = 0; vector<int> minv(m + 1, INT_MAX); vector<bool> used(m + 1, false); do { used[j0] = true; int i0 = p[j0], delta = INT_MAX, j1; for (int j = 1; j <= m; ++j) { if (!used[j]) { int cur = matrix[i0][j] - u[i0] - v[j]; if (cur < minv[j]) { minv[j] = cur; way[j] = j0; } if (minv[j] < delta) { delta = minv[j]; j1 = j; } } } for (int j = 0; j <= m; ++j) { if (used[j]) { u[p[j]] += delta; v[j] -= delta; } else { minv[j] -= delta; } } j0 = j1; } while (p[j0] != 0); do { int j1 = way[j0]; p[j0] = p[j1]; j0 = j1; } while (j0); } return -v[0]; }

4.2 二分图常见变形问题

1. 多重匹配：每个顶点可以匹配多个边
2. 稳定婚姻问题：考虑优先级的匹配
3. 三维匹配：扩展到更高维度的匹配问题
4. 网络流模型：将二分图问题转化为最大流问题

对于网络流解法，通常建立超级源点和超级汇点：

超级源点 -> 左部顶点 -> 右部顶点 -> 超级汇点

使用Dinic算法求解最大流：

struct Edge { int to, rev, flow, cap; }; vector<vector<Edge>> g; vector<int> level, ptr; void addEdge(int u, int v, int cap) { Edge a{v, (int)g[v].size(), 0, cap}; Edge b{u, (int)g[u].size(), 0, 0}; g[u].push_back(a); g[v].push_back(b); } bool bfs(int s, int t) { level.assign(g.size(), -1); queue<int> q; level[s] = 0; q.push(s); while (!q.empty()) { int v = q.front(); q.pop(); for (Edge &e : g[v]) { if (level[e.to] < 0 && e.flow < e.cap) { level[e.to] = level[v] + 1; q.push(e.to); } } } return level[t] >= 0; } int dfs(int v, int t, int flow) { if (v == t) return flow; for (; ptr[v] < g[v].size(); ++ptr[v]) { Edge &e = g[v][ptr[v]]; if (level[e.to] == level[v] + 1 && e.flow < e.cap) { int f = dfs(e.to, t, min(flow, e.cap - e.flow)); if (f > 0) { e.flow += f; g[e.to][e.rev].flow -= f; return f; } } } return 0; } int maxFlow(int s, int t) { int flow = 0; while (bfs(s, t)) { ptr.assign(g.size(), 0); while (int f = dfs(s, t, INT_MAX)) { flow += f; } } return flow; }

5. 竞赛实战技巧与调试方法

5.1 二分图问题识别模式

在比赛中快速识别二分图问题的特征包括：

1. 明显的两类对象及其关系（如学生与课程）
2. 棋盘类问题的行列关系
3. 匹配、覆盖、分配等关键词
4. 冲突图的反图可能是二分图

5.2 常见错误与调试技巧

1. 顶点编号问题：确保左右两部顶点编号不冲突
2. 图存储方式：邻接表比邻接矩阵更节省空间
3. 初始化问题：每次DFS前重置访问标记
4. 非连通图处理：需要检查所有连通分量

调试时可以输出中间结果：

• 染色法的染色结果
• 匹配过程的中间状态
• 网络流中的流量分布

5.3 性能优化策略

1. 输入优化：使用快速IO方法
2. 内存预分配：避免动态扩容
3. 算法选择：根据数据规模决定使用匈牙利还是HK算法
4. 剪枝策略：提前终止不可能产生更优解的分支

// 快速IO示例 ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

二分图作为信奥赛C++提高组的重要考点，需要选手深入理解其原理并熟练掌握多种实现方法。在实际比赛中，灵活运用二分图模型往往能将复杂问题简化为经典图论问题，从而高效求解。建议通过大量练习来培养对二分图问题的敏感度，并积累各种变形问题的解决经验。