华为OD机试“素数伴侣”题解：二分图最大匹配与匈牙利算法实战

1. 项目概述从一道真题看华为OD机试的核心考察点最近在帮几个准备华为OD机试的朋友做模拟训练发现“素数伴侣”这道题出现的频率相当高尤其是在B卷和C卷中。这道题乍一看名字有点“浪漫”但实际是考察图论中“二分图最大匹配”的经典应用再结合数论中的素数判断可以说是算法与数据结构基本功的“试金石”。很多朋友卡在这道题上不是因为算法本身多难而是没能在有限时间内将问题抽象成正确的模型并写出高效、无bug的代码。今天我就结合自己多次模拟和辅导的经验用C来彻底拆解这道“素数伴侣”不仅给出能AC通过所有测试用例的代码更重要的是分享解题的完整思路、编码中的关键细节以及那些容易踩坑的地方。无论你是刚开始刷题还是已经有一定基础但在图论问题上感到棘手相信这篇详尽的解析都能帮你打通任督二脉。这道题的核心场景是给定一组正整数你需要将它们两两配对要求每对数字之和必须是一个素数。目标是找到能够组成的最多配对数量。这听起来像是一个组合优化问题暴力枚举所有配对方式在数据量稍大时比如超过10个数就完全不可行。因此我们必须寻找更聪明的办法。这恰恰是华为OD机试的典型风格不追求偏难怪的算法但要求你扎实掌握基础数据结构数组、链表、图和经典算法排序、搜索、动态规划、图算法并能在实际问题中灵活应用。2. 核心思路拆解为何是二分图匹配拿到题目第一步不是急着写代码而是理解问题本质。为什么“素数伴侣”会指向“二分图最大匹配”我们来一步步推理。2.1 问题转化与建模过程首先我们有一堆数字。配对的条件是两个数之和为素数。这里有一个非常重要的观察素数中除了2是偶数其他所有素数都是奇数。而一个奇数只能由一个偶数和一个奇数相加得到因为偶数偶数偶数奇数奇数偶数偶数奇数奇数。由于素数伴侣要求“和为素数”而素数绝大部分是奇数因此能配对的两个人很可能一个是奇数一个是偶数。这里有一个特例数字2。2是素数也是偶数。如果一对数字的和是2那么这两个数只能是1和1。但在题目给定的正整数集合中通常不会出现两个1即使出现112这个配对也符合“奇偶配对”的模式1是奇数1是奇数但和为偶数2。更重要的是题目给定的数字范围通常远大于2所以和为2的情况几乎不会成为主流。因此我们可以得到一个强有力的结论有效的配对绝大多数情况下都发生在一个奇数和一个偶数之间。基于这个观察我们可以将所有数字分成两个集合奇数集合和偶数集合。配对只能发生在跨集合的奇数和偶数之间同集合内的奇数与奇数、偶数与偶数之和为偶数而大于2的偶数不是素数。这完美契合了“二分图”的定义图中的所有顶点可以划分成两个互不相交的子集奇数和偶数并且所有的边代表可以配对都连接着这两个子集中的顶点。于是原始问题“找到最多的配对对数”就转化为了图论中的一个经典问题在这个二分图中找到最大的匹配数即最多能选出多少条边使得这些边没有公共的顶点。这就是著名的“二分图最大匹配”问题。2.2 算法选型匈牙利算法 vs. 最大流对于二分图最大匹配有两种主流算法匈牙利算法Hungarian Algorithm和基于最大流Max Flow的算法如Edmonds-Karp或Dinic算法。匈牙利算法这是解决二分图最大匹配最经典、最直接的算法。它的核心思想是“腾挪”和“增广”。通过深度优先搜索DFS或广度优先搜索BFS尝试为当前左边的每个点比如奇数寻找右边的匹配点偶数。如果心仪的右边点已经被匹配就去“协商”看看能否让之前匹配它的左边点换一个对象从而腾出位置。匈牙利算法实现相对简单时间复杂度为O(V*E)其中V是顶点数E是边数。在本题的数据范围内通常N100完全够用且代码简洁易于理解和调试。最大流算法我们可以构建一个流网络源点连接所有奇数点容量为1所有奇数点连接到能配对的偶数点容量为1所有偶数点连接到汇点容量为1。那么这个网络的最大流值就等于最大匹配数。使用Dinic等算法效率也很高。但对于本题而言杀鸡用牛刀增加了建图的复杂度。注意在华为OD的机试环境中稳定、简洁、易调试的代码往往比追求极致的理论时间复杂度更重要。考场上的时间非常紧张一个清晰的匈牙利算法实现远比一个复杂但可能更快的最大流算法要可靠。因此我们毫不犹豫地选择匈牙利算法。2.3 素数判断的优化另一个关键点是“素数判断”。我们需要频繁判断两个数之和是否为素数。最朴素的方法是对于每个和sum从2遍历到sqrt(sum)看是否有整除因子。但频繁调用会带来性能开销。更高效的做法是预处理素数表。根据题目输入数字的范围题目通常会说明比如每个数不超过30000我们可以估算出最大可能的和比如60000。使用经典的“埃拉托斯特尼筛法”Sieve of Eratosthenes预处理出一个布尔数组isPrimeisPrime[i]true表示i是素数。这样在判断任意两个数ab时只需要O(1)的时间查询isPrime[ab]即可将判断时间复杂度从O(√n)降到了O(1)用空间换取了宝贵的时间。3. C实现详解与关键代码解析思路清晰后我们开始动手实现。我会将代码分成几个逻辑模块并逐一解释。3.1 数据结构设计与全局变量#include iostream #include vector #include cmath #include cstring // for memset using namespace std; const int MAX_SUM 60010; // 假设两数最大和不超过60000适当留余量 bool isPrime[MAX_SUM]; // 素数表 vectorint odds, evens; // 分别存储奇数和偶数 vectorvectorint graph; // 邻接表graph[i]存储第i个奇数可以配对的偶数索引 vectorint match; // match[e] o表示偶数e当前匹配的奇数索引o-1表示未匹配 vectorbool visited; // DFS访问标记MAX_SUM根据题目可能的数据范围设定。如果题目明确数字范围可以精确计算。isPrime全局素数表在程序开始时用筛法初始化。odds,evens分别存放输入中的奇数和偶数。注意我们存放的是数字本身的值而不是索引。graph这是一个关键的邻接表。graph[i]是一个向量里面存放的是所有能与第i个奇数配对的偶数在evens数组中的索引。为什么存索引而不是值因为后续匈牙利算法需要基于索引进行匹配。match记录匹配关系。match[even_index] odd_index表示这个偶数当前匹配给了哪个奇数。初始化为-1。visited在匈牙利算法的DFS过程中标记偶数是否在当前一轮的增广路搜索中被访问过防止死循环。3.2 素数表初始化埃拉托斯特尼筛法void initPrimeTable() { // 初始化所有数为素数 fill(isPrime, isPrime MAX_SUM, true); isPrime[0] isPrime[1] false; // 0和1不是素数 for (int i 2; i * i MAX_SUM; i) { if (isPrime[i]) { // 将i的倍数标记为非素数 for (int j i * i; j MAX_SUM; j i) { isPrime[j] false; } } } }这段代码是标准的筛法。注意内层循环从j i * i开始因为小于i*i的合数已经被更小的质因数标记过了。这是一个常见的微优化。3.3 构建二分图邻接表这是将问题转化为图模型的核心步骤。void buildGraph() { int oddSize odds.size(); int evenSize evens.size(); graph.resize(oddSize); // 图的大小等于奇数个数 for (int i 0; i oddSize; i) { for (int j 0; j evenSize; j) { int sum odds[i] evens[j]; if (isPrime[sum]) { // 奇数i和偶数j可以配对将偶数j的索引加入奇数i的邻接表 graph[i].push_back(j); } } } }两层循环遍历所有奇偶组合判断和是否为素数如果是则在邻接表中建立一条边。时间复杂度是O(O*E)其中O和E分别是奇数和偶数的数量。在N100时完全可接受。3.4 匈牙利算法核心实现这是整个程序的“发动机”。bool dfs(int oddIdx) { // 尝试为奇数oddIdx寻找匹配的偶数 for (int evenIdx : graph[oddIdx]) { // 遍历所有可能配对的偶数 if (!visited[evenIdx]) { visited[evenIdx] true; // 如果这个偶数还没有被匹配或者可以为它当前的匹配对象找到新的偶数 if (match[evenIdx] -1 || dfs(match[evenIdx])) { // 匹配成功 match[evenIdx] oddIdx; return true; } } } // 所有可能的偶数都尝试过了无法为当前奇数找到匹配 return false; } int hungarian() { int res 0; // 最大匹配数 match.assign(evens.size(), -1); // 初始化所有偶数未匹配 for (int i 0; i odds.size(); i) { visited.assign(evens.size(), false); // 每轮DFS前清空访问标记 if (dfs(i)) { res; } } return res; }dfs(int oddIdx)函数为指定的奇数索引为oddIdx寻找一个匹配的偶数。它遍历这个奇数所有可能配对的偶数通过graph[oddIdx]获得。对于每个偶数如果它在本轮搜索中还没被访问过!visited[evenIdx]就标记为已访问。然后检查这个偶数的状态如果它还没被匹配match[evenIdx] -1那太好了直接匹配上返回true。如果它已经被匹配了我们就“递归地”去问它现在的匹配对象那个奇数match[evenIdx]“你能不能换一个对象” 即调用dfs(match[evenIdx])。如果那个奇数能找到新的偶数那么它就会“让出”当前这个偶数从而让最初的奇数oddIdx匹配成功。这就是“协商”或“腾挪”的过程。如果所有可能的偶数都尝试失败则返回false。hungarian()函数主流程。遍历每一个奇数尝试为它寻找匹配。每成功一次匹配数res就加一。注意每次为一个新的奇数寻找匹配前必须重置visited数组。因为visited数组的作用是防止在单次DFS中进入循环它记录的是在当前这轮“为奇数i找对象”的尝试中哪些偶数已经被考虑过了。3.5 主函数与输入处理int main() { initPrimeTable(); // 第一步初始化素数表 int n; while (cin n) { // 支持多组输入符合机试常见格式 odds.clear(); evens.clear(); for (int i 0; i n; i) { int num; cin num; if (num % 2 1) { odds.push_back(num); } else { evens.push_back(num); } } // 如果奇数或偶数集合为空则无法形成任何配对除了112的特例这里忽略 if (odds.empty() || evens.empty()) { cout 0 endl; continue; } buildGraph(); // 第二步构建邻接表 int maxPairs hungarian(); // 第三步运行匈牙利算法 cout maxPairs endl; } return 0; }主函数的逻辑很清晰初始化素数表只需一次。读取输入n和n个数字按奇偶性分别存入odds和evens。边界情况处理如果奇数或偶数列表有一个为空最大匹配数显然为0。调用buildGraph构建从奇数到偶数的邻接表。调用hungarian计算最大匹配数并输出。4. 完整可运行代码整合将上述所有模块组合起来就是一份完整的、可以直接在华为OD机试平台上提交的C代码。#include iostream #include vector #include cmath #include cstring using namespace std; const int MAX_SUM 60010; bool isPrime[MAX_SUM]; void initPrimeTable() { fill(isPrime, isPrime MAX_SUM, true); isPrime[0] isPrime[1] false; for (int i 2; i * i MAX_SUM; i) { if (isPrime[i]) { for (int j i * i; j MAX_SUM; j i) { isPrime[j] false; } } } } bool dfs(int oddIdx, const vectorvectorint graph, vectorint match, vectorbool visited) { for (int evenIdx : graph[oddIdx]) { if (!visited[evenIdx]) { visited[evenIdx] true; if (match[evenIdx] -1 || dfs(match[evenIdx], graph, match, visited)) { match[evenIdx] oddIdx; return true; } } } return false; } int hungarian(const vectorvectorint graph, int evenSize) { int res 0; vectorint match(evenSize, -1); for (int i 0; i graph.size(); i) { vectorbool visited(evenSize, false); if (dfs(i, graph, match, visited)) { res; } } return res; } int main() { initPrimeTable(); int n; while (cin n) { vectorint odds, evens; int num; for (int i 0; i n; i) { cin num; (num % 2) ? odds.push_back(num) : evens.push_back(num); } if (odds.empty() || evens.empty()) { cout 0 endl; continue; } // 构建邻接表 graph[odd_index] - list of even_index vectorvectorint graph(odds.size()); for (int i 0; i odds.size(); i) { for (int j 0; j evens.size(); j) { if (isPrime[odds[i] evens[j]]) { graph[i].push_back(j); } } } int maxPairs hungarian(graph, evens.size()); cout maxPairs endl; } return 0; }5. 常见问题与调试技巧实录在实际编码和调试过程中我遇到过不少坑这里总结一下帮你提前避雷。5.1 数组越界与素数表大小这是最容易出错的地方之一。MAX_SUM的值必须足够大要大于输入中可能出现的两个最大数之和。如果题目说每个数不超过30000那么MAX_SUM至少需要60001。我习惯设置得稍大一些如60010以防边界情况。如果MAX_SUM设置小了在访问isPrime[ab]时就会发生数组越界导致运行时错误Runtime Error或结果错误。实操心得在机试中如果题目没有明确给出数据范围可以通过观察样例输入的最大值来估算。或者更稳妥的方法是在读取输入时动态记录最大值maxNum然后设定MAX_SUM 2 * maxNum 5。但在考场上为了代码简洁和速度通常根据经验预设一个足够大的值如100000也是可行的只要不超出内存限制。5.2 奇偶分组的特例处理我们的核心逻辑建立在“有效配对必为奇偶配对”上。但有两个特例需要考虑数字11是奇数。1122是素数。这意味着两个1可以配对且它们都是奇数违反了我们的奇偶分组原则。但在实际题目中输入通常不会给出重复的1即使给出我们也可以这样处理在奇偶分组后如果奇数集合里有超过1个1我们可以先内部消化掉这些1。一个简单的做法是统计1的个数count1那么这些1最多可以组成count1/2对。剩下的奇数包括可能剩下的1个1再和偶数进行匈牙利匹配。不过在华为OD的历史真题中输入数据似乎规避了这种情况所以按标准奇偶分组做通常也能AC。但心里要有这根弦。数字22是偶数也是素数。如果有一个奇数x使得x2是素数比如x1, 3, 5...那么(x,2)是有效的奇偶配对我们的模型能正确处理。如果出现两个2224不是素数则无法配对也无影响。避坑技巧如果担心特例可以在代码开头加入对输入数字1的个数的判断进行特殊处理。但在时间有限的机试中如果样例能过通常可以假设测试数据是“友好”的。优先保证主体算法的正确性和完整性。5.3 匈牙利算法中的visited数组重置这是一个经典的细节错误。在hungarian函数中for循环遍历每个奇数在调用dfs(i)之前必须重新初始化visited数组为全false。visited数组的作用域是单次DFS增广路径搜索目的是防止在寻找一条增广路时走回头路。如果忘记重置之前搜索留下的标记会影响后续搜索导致算法错误可能漏掉一些本应存在的匹配。5.4 输入输出格式与多组测试用例华为OD机试的题目经常支持多组测试用例输入直到文件结束EOF。代码中的while (cin n)就是用来处理这种情况的。如果你的代码只处理一组数据当后台有多组测试时只会判断第一组正确导致得分不全。另外注意输出格式通常就是直接输出一个整数末尾换行。不要画蛇添足输出“Result: ”之类的提示语。5.5 性能与复杂度分析让我们分析一下代码的复杂度确保能在规定时间内运行。素数筛法O(MAX_SUM log log MAX_SUM)这是一次性的开销可忽略。建图O(O * E)其中O是奇数个数E是偶数个数。最坏情况O≈E≈N/2≈50则操作约2500次非常快。匈牙利算法最坏复杂度O(V * E)这里V是奇数个数OE是图中的总边数即所有graph[i]的长度之和。在最稠密的情况下所有奇偶和都是素数边数可达O * E ≈ 2500。那么算法复杂度大约为50 * 2500 125,000次操作对于计算机来说瞬间完成。所以整体算法对于N100的规模是游刃有余的。5.6 调试与测试用例设计自己设计几个测试用例来验证代码基础用例输入4 [2, 5, 6, 13]。奇数[5,13]偶数[2,6]。527(素数)5611(素数)13215(非素数)13619(素数)。图奇数0(5)连接偶数0(2)、1(6)奇数1(13)连接偶数1(6)。最大匹配是2对5-2, 13-6或5-6, 13-2。输出应为2。边界用例1输入2 [1, 1]。两个奇数1和2是素数。但我们的标准算法会将其分到奇数组偶数组为空输出0。这就是上面讨论的特例。如果题目包含此用例则需要特殊处理。边界用例2输入3 [2, 4, 8]。全是偶数奇数组为空输出0。较大规模用例随机生成100个[1, 30000]的数用你的程序跑一下看看是否能在短时间内输出结果并且结果合理可以自己用暴力算法对小规模数据验证。在本地调试时可以将MAX_SUM设小并打印出graph邻接表和最终的match数组来跟踪匈牙利算法的执行过程这对于理解算法非常有帮助。最后在华为OD的机试环境中选择正确的语言版本如C11/14/17使用标准的头文件避免使用非标准的编译器扩展特性确保代码的可移植性。将上面的完整代码粘贴到答题框仔细检查后提交这道“素数伴侣”的满分就应该稳稳到手了。这道题的精髓不在于代码多复杂而在于能否完成从问题描述到二分图模型的关键抽象以及能否无误地实现匈牙利算法。希望这篇超详细的解析能让你彻底掌握它。