题解 | 素数伴侣

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

// 判断一个数是否为素数
bool is_prime(uint32_t a) 
{
    if (a <= 1) return false;
    if (a == 2) return true;
    if (a % 2 == 0) return false;
    for (uint32_t i = 3; i * i <= a; i += 2) {
        if (a % i == 0) return false;
    }
    return true;
}

// 匈牙利算法的 DFS 部分
bool dfs(int u, const vector<vector<int>>& graph, vector<int>& match, vector<bool>& visited) 
{
    for (int v : graph[u]) {
        if(!visited[v]) {
            visited[v] = true;
            // 如果该偶数未匹配，或者可以找到增广路径
            if (match[v] == -1 || dfs(match[v], graph, match, visited)) {
                match[v] = u; // 匹配成功
                return true;
            }
        }
    }
    return false;
}

int main() 
{
    int n;
    cin >> n;
    vector<uint32_t> nums(n);
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
    }

    // 分离奇数和偶数
    vector<uint32_t> odds, evens;
    for (uint32_t num : nums) {
        if (num % 2 == 0) {
            evens.push_back(num);
        } else{
            odds.push_back(num);
        }
    }

    // 构建邻接表：每个奇数可以与哪些偶数组成素数对
    int m = odds.size();
    int k = evens.size();
    vector<vector<int>> graph(m); // 奇数索引 -> 偶数索引
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < k; ++j) {
            if(is_prime(odds[i] + evens[j])) {
                graph[i].push_back(j);
            }
        }
    }

    // 匈牙利算法求最大匹配
    vector<int> match(k, -1); // match[v] 表示偶数 evens[v] 匹配的奇数索引
    int result = 0;
    for (int u = 0; u < m; ++u) {
        vector<bool> visited(k, false); // 每次DFS都需要新的访问标记
        if(dfs(u, graph, match, visited)) {
            ++result; // 找到一条增广路径，匹配数+1
        }
    }

    cout << result << endl;
    return 0;
}