题解 | #素数伴侣#

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

// int main() {
//     // int n;
//     // cin >> n;
//     // vector<int> res;
//     // for (int i = 0; i < n; i++) {
//     //     int num;
//     //     cin >> num;
//     //     res.push_back(num);
//     // }


// }
// // 64 位输出请用 printf("%lld")
#include <iostream>
#include<vector>
using namespace std;
bool isprime(int i) { //判断是否为素数
    for (int j = 2; j * j <= i; j++) {
        if (i % j == 0)
            return false;
    }
    return true;
}
bool find(const int& n, vector<vector<bool>>& map, vector<int>& match,
          vector<bool>& visit) {
    for (int i = 0; i < match.size(); i++) {
        if (!visit[i] &&
                map[i][n]) { //当前偶数未被访问过并且能和奇数n是素数伴侣
            visit[i] = true;
            if (match[i] == -1 ||
                    find(match[i], map, match,
                         visit)) { //当前偶数没有匹配或能给被抛弃的奇数找到新的偶数
                match[i] = n;//建立偶数和奇数之间的连接
                return true;
            }
        }
    }
    return false;
}
int main() {
    int n = 0;
    while (cin >> n) {
        int k = 0; //读取数据
        vector<int> even;
        vector<int> odd;
        int count = 0; //匹配对数
        while (n--) { //逐个输入按奇偶分类
            cin >> k;
            if (k % 2 == 0) {
                odd.push_back(k);
            } else {
                even.push_back(k);
            }
        }
        if (odd.empty() ||
                even.empty()) { //奇数或偶数为空则不会有素数伴侣
            cout << count << endl;
            continue;
        }
        vector<vector<bool>> map(even.size(), vector<bool>(odd.size(), false));
        for (int i = 0; i < even.size();
                i++) { //建立关系图，找出所有可能的连接
            for (int j = 0; j < odd.size(); j++) {
                if (isprime(even[i] + odd[j])) {
                    map[i][j] = true;
                }
            }
        }
        vector<int> match(even.size(), -1);
        for (int i = 0; i < odd.size(); i++) {
            vector<bool> visit(even.size(),
                               false);//建立在当前奇数下对偶数的访问情况
            if (find(i, map, match, visit)) {
                count++;
            }
        }
        cout << count << endl;
    }
    return 0;
}