题解 | #素数伴侣#

#include <iostream>
using namespace std;
#include <cmath>
#include <vector>
#include <map>
bool isPri(int x) {
    for (int i = 2; i <= sqrt(x); i++) {
        if (x % i == 0) {
            return false;
        }
    }
    return true;
}

bool find(const int odd,const vector<vector<bool>> & match,vector<bool> & used,vector<int> & eoPair){
    for(int i = 0; i < used.size();i++){
        if(match[i][odd] && !used[i]){
            used[i] = true;
            if(eoPair[i] == -1 || find(eoPair[i],match,used,eoPair)){
                eoPair[i] = odd;
                return true;
            }
        }
    }
    return false;
}

int main() {
    int num;
    cin >> num;
    vector<int> evens;//偶数数组
    vector<int> odds;//奇数数组
    while(cin >> num){
        if(num%2 == 0){
            evens.push_back(num);
        }
        else{
            odds.push_back(num);
        }
    }
    if(evens.size() == 0 || odds.size() == 0){
        cout << "0" << endl;
        return 0;
    }

    vector<vector<bool>> match(evens.size(),vector<bool>(odds.size(),false));
    for(int i = 0;i < evens.size();i++){
        for(int j = 0; j < odds.size();j++){
            if(isPri(evens[i] + odds[j])){
                match[i][j] = true;
            }
        }
    }
    int cnt = 0;
    vector<int> eoPair (evens.size(),-1);
    for(int i = 0; i<odds.size();i++){
        vector<bool> used(evens.size(),false);
        if(find(i,match,used,eoPair)){
            cnt++;
        }
    }

    cout << cnt << endl;
}

思路基本和其他题解一样，但是有个细节，需要用引用来节省程序空间，才能通过测试

算法逻辑比较暴力，背一下得了

简单描述一下解题思路（匈牙利算法）

首先必须是一奇一偶相加才可能会是素数，所以对输入进行一个奇偶分组，同时在只有奇数/偶数的情况输出0并直接return

分组后，使用一个match的二维数组记录一下2数相加是否为质数的情况(用空间节省时间）,另一种算法则是每次都检查

对于每个奇数（odd），检查所有偶数(第一层循环)，如果符合相加为素且偶数没被用过的条件，则修改该偶数的used，并继续检查该偶数是否已经有过配对(找到这个偶数所配对的奇数)，如果之前有，则取出它的所对应的奇数（eoPair[i]），再次递归搜索，如果为这个奇数（eoPair[i]）找到了新的（未使用）偶数进行配对，则为这个偶数重新配对(odd)。

有点绕，建议多看几个题解