题解 | #素数伴侣# 二分图匹配+匈牙利算法

#include <iostream>
#include <vector>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int maxn = 30010;
int n, a;
vector<int> odd, even;
bool vis[maxn];
int match[maxn];
bool np[maxn * 2] = {true, true, false};
void findPrimes() {
    for (int i = 2; i < maxn * 2; ++i)
        if (!np[i]) // 是素数
            for (int j = i * i; j < maxn * 2; j += i)
                np[j] = true;
}
bool dfs(int x) { 
    for (int j = 0; j < even.size(); ++j) { // odd[i]都可能与even[j]构成素数 
        int y = even[j]; 
        if (!vis[y] && !np[x + y]) {
            vis[y] = true; 
            if (!match[y] || dfs(match[y])) {
                match[y] = x; return true;
            }
        }
    }
    return false; // 找不到和odd[i]匹配的even[j]
}
int main() {
    cin >> n;
    findPrimes(); 
    for (int i = 0; i < n; ++i) {
        cin >> a;
        if (a & 1) odd.push_back(a);
        else even.push_back(a);
    } 
    int ans = 0;
    for (int i = 0; i < odd.size(); ++i) {
        for (int j = 0; j < 30010; ++j) vis[j] = false;
        if (dfs(odd[i])) ++ans;
    }
    printf("%d", ans);
}