华为机试：素数伴侣的二分图匹配解法

题目描述

若两个正整数的和为素数，则这两个正整数称为'素数伴侣'，例如 2 和 5、6 和 13。题目要做的事很直接：从给定的 N 个正整数里，尽可能多地配成这样的组合，输出最多能组成多少对。

输入：

有一个正偶数 N（N≤100），表示待挑选的自然数个数。后面跟着 N 个数字，范围是 [2,30000]。

输出：

输出一个整数 K，表示'最佳方案'里素数伴侣的对数。

解题思路

这题看起来像排列组合，实际上是标准的二分图最大匹配。关键点不在'怎么配'，而在先把图拆对。

除了 2 以外，素数都是奇数。题目里的数都不小于 2，所以两个数之和如果是素数，基本就得是奇数；而奇数只能由一奇一偶相加得到。也就是说，奇数和偶数天然分属两边，能连边的只会是奇偶配对。

于是问题就变成了：把奇数放左边，偶数放右边，若两数之和是素数，就在它们之间连一条边。接下来要找的是最大匹配，也就是最多能选出多少条互不冲突的边。

实现上用 DFS 找增广路就够了。数据规模不大，匈牙利算法的写法完全能过，而且代码比别的图论套路更顺手。

代码实现

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

vector<int> G[105];
int pre[105];
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] = 1;
            if (pre[neighbor] == 0 || dfs(pre[neighbor])) {
                pre[neighbor] = k;
                return true;
            }
        }
    }
    return false;
}

int main() {
    bool isprime[80000];
    memset(isprime, 0, sizeof(isprime));
    for (int i = 2; i <= 80000; i++) {
        int j;
        for (j = 2; j < i; j++) {
            if (i % j == 0 || j * j > i) {
                break;
            }
        }
        if (j * j > i) {
            isprime[i] = 1;
        }
    }

    int N;
    int nums[105];
    int temp;

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

        for (int i = 1; i <= N; ++i) {
            for (int j = i + 1; j <= N; ++j) {
                if (isprime[nums[i] + nums[j]]) {
                    if (nums[i] % 2 == 1) {
                        G[i].push_back(j);
                    } else {
                        G[j].push_back(i);
                    }
                }
            }
        }

        memset(pre, 0, sizeof(pre));
        int count = 0;
        for (int i = 1; i <= N; ++i) {
            memset(used, 0, sizeof(used));
            if (dfs(i)) count++;
        }

        cout << count << endl;

        for (int i = 1; i <= N; ++i) G[i].clear();
    }
    return 0;
}

调试时要盯住的几个点

第一，素数表最好提前算好。N 只有 100，但数字最大到 30000，任意两数之和会到 60000，预处理一次比每次现判省事得多。

第二，建图方向别弄乱。这里不是把所有能配对的数都扔进同一个邻接表，而是只保留奇数到偶数的边。这样 DFS 的起点就明确了，匹配过程也不会乱计数。

第三，多组输入时记得清空状态。pre、used 和 G 都不能带到下一组，不然结果会飘得很明显。

这题的套路很固定，难点主要在把'素数伴侣'识别成二分图匹配。识别出来以后，代码其实不长，思路也比较稳。