华为机试题解：素数伴侣（最大二分图匹配）

题目描述

若两个正整数的和为素数，则这两个正整数称之为'素数伴侣'，如 2 和 5、6 和 13，它们能应用于通信加密。现在密码学会请你设计一个程序，从已有的 N（N 为偶数）个正整数中挑选出若干对组成'素数伴侣'，挑选方案多种多样，例如有 4 个正整数：2，5，6，13，如果将 5 和 6 分为一组中只能得到一组'素数伴侣'，而将 2 和 5、6 和 13 编组将得到两组'素数伴侣'，能组成'素数伴侣'最多的方案称为'最佳方案'，当然密码学会希望你寻找出'最佳方案'。

输入： 有一个正偶数 N（N≤100），表示待挑选的自然数的个数。后面给出具体的数字，范围为 [2,30000]。

输出： 输出一个整数 K，表示你求得的'最佳方案'组成'素数伴侣'的对数。

解题思路

这道题看似是组合优化，实则是一个经典的二分图最大匹配问题。关键在于发现数字之间的内在联系。

首先，除了 2 以外，所有的素数都是奇数。题目中给出的数字范围最小是 2，所以任意两个数之和至少是 4。这意味着我们要找的和必须是大于等于 4 的素数，也就是奇素数。

既然和是奇数，那么加数必然是一奇一偶（因为 奇 + 奇 = 偶，偶 + 偶 = 偶）。这就把我们的数字分成了两个互不相交的集合：奇数集合和偶数集合。只有当奇数和偶数配对时，它们的和才可能是素数。

这样一来，问题就转化为了在一个二分图中寻找最大匹配。我们可以把奇数放在左部，偶数放在右部，如果某一对奇偶数之和为素数，就在它们之间连一条边。我们的目标就是找出最多的边，使得没有两条边共用一个顶点。

具体实现上，我们采用深度优先搜索（DFS）配合回溯来寻找增广路，这是求解二分图最大匹配的标准做法（匈牙利算法的一种变体）。

代码实现

下面是完整的 C++ 解决方案。注意这里使用了 while(cin >> N) 来处理多组测试数据，这也是机试常见的输入方式。

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;

// 邻接表存储图
vector<int> G[105];
// pre 数组记录匹配关系，pre[v]=u 表示 v 匹配了 u
int pre[105];
// used 数组标记 DFS 过程中是否访问过
bool used[105];

// 深度优先搜索寻找增广路
bool dfs(int k) {
    for (int i = 0; i < G[k].size(); ++i) {
        int neighbor = G[k][i];
        if (!used[neighbor]) {
            used[neighbor] = ;
            
             (pre[neighbor] ==  || (pre[neighbor])) {
                pre[neighbor] = k;
                 ;
            }
        }
    }
     ;
}

{
    
    
     isprime[];
    (isprime, , (isprime));
     ( i = ; i <= ; i++) {
         j;
         (j = ; j < i; j++) {
             (i % j ==  || j * j > i) {
                ;
            }
        }
        
         (j * j > i) {
            isprime[i] = ;
        }
    }

     N;
     nums[];
     temp;
    
    
     (cin >> N) {
         ( i = ; i <= N; ++i) {
            cin >> temp;
            nums[i] = temp;
        }

        
        
         ( i = ; i <= N; ++i) {
             ( j = i + ; j <= N; ++j) {
                 (isprime[nums[i] + nums[j]]) {
                    
                    
                    
                    
                     (nums[i] %  == ) {
                        G[i].(j);
                    }  {
                        G[j].(i);
                    }
                }
            }
        }

        
        (pre, , (pre));
         count = ;
         ( i = ; i <= N; ++i) {
            (used, , (used));
             ((i)) count++;
        }

        cout << count << endl;

        
         ( i = ; i <= N; ++i) G[i].();
    }
     ;
}