题解 | #素数伴侣#

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

bool isPrime(int a) {
    if(a < 4) return true;
    int n = 2;
    while(n*n <= a) {
        if(a%n == 0) return false;
        ++n;
    }
    return true;
}

/*查找奇数num能否在偶数中找到匹配结果*/
bool find(int num, const vector<vector<bool>> &map, vector<bool> &visit, vector<int> &match) {
    for(int i=0; i<match.size(); ++i) { // 遍历偶数
        if(!visit[i] && map[i][num]) {  // 第i个偶数没有访问且能和num匹配
            visit[i] = true;    // 第i个偶数被用了
            if(match[i] == -1 || find(match[i], map, visit, match)) {
                /*这个偶数还没有匹配对象，或者这个偶数的匹配对象
                能递归找到其他匹配，则更新这个偶数的匹配对象，
                并认为num能找到匹配对象
                
                这个递归应该是使得匹配数最大的原因，但是还没想明白-_-!*/
                match[i] = num;
                return true;
            }
        }
    }
    return false;
}
int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    // 显然这里的素数必然是奇数与偶数的组合，可以将问题转换为二分图匹配
    vector<int> odds;   // 奇数
    vector<int> evens;  // 偶数
    int count = 0;
    for(int i=0; i<n; ++i) {
        cin >> nums[i];
        if(nums[i] % 2) odds.push_back(nums[i]);
        else evens.push_back(nums[i]);
    }
    if(odds.empty() || evens.empty()) {
        cout << count << endl;
        return count;
    }
    vector<vector<bool>> map(evens.size(), vector<bool>(odds.size(), false));   // 二维数组记录偶数i与奇数j的匹配结果map[i][j]
    for(int i=0; i<evens.size(); ++i) {
        for(int j=0; j<odds.size(); ++j) {
            map[i][j] = isPrime(evens[i] + odds[j]);
        }
    }

    // 匈牙利算法？
    vector<int> match(evens.size(), -1);
    for(int i=0; i<odds.size(); ++i) {
        vector<bool> visit(evens.size(), false);
        if(find(i, map, visit, match)) {
            ++count;
        }
    }

    cout << count << endl;
    
    return 0;
}
// 64 位输出请用 printf("%lld")

二分图最大匹配的关键函数

bool find(int num, const vector<vector<bool>> &map, vector<bool> &visit, vector<int> &match)

还没想明白，留作记录