题解：P5771 [JSOI2016] 反质数序列

· · 题解

显然一个质数只可能分解成一奇一偶两个数相加（2 除外），考虑记录所有偶数和奇数（由于 1 + 1 = 2，所以只能存在一个 1），将奇数设为左部点，偶数设为右部点。若一个左部点加上一个右部点为质数，就连边。最大匹配就是不能同时有的对数，所以答案就是数字总数减去最大匹配。

:::info[Code]

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

constexpr int MAXN = 3005;
constexpr int MAXV = 1e5 + 10;

int with[MAXN], vis[MAXN], n, a[MAXN], head[MAXN], tot = 0;
bitset<MAXV << 1> unPrime;
vector<int> Prime, edge[MAXN];

inline void init() { // 预处理质数
    for (register int i = 2; i <= MAXV << 1; ++i) {
        if (!unPrime[i]) Prime.push_back(i);
        for (int p : Prime) {
            if (p * i > (MAXV << 1)) break;
            unPrime[p * i] = true;
            if (!(i % p)) break;
        }
    }
}

inline bool solve(int u, int t) { // 匈牙利
    if (vis[u] == t) return false;
    vis[u] = t;
    for (auto v : edge[u]) 
        if (!with[v] || solve(with[v], t)) {with[v] = u; return true;}
    return false;
}

int main() {
    ios :: sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n, init();
    int odd[MAXN], even[MAXN], os = 0, es = 0;
    bool is1 = false;

    for (register int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        if (x == 1) {
            if (!is1) odd[++os] = x, is1 = true;
        } else if (x & 1) odd[++os] = x;
        else even[++es] = x;
    }

    int ans = os + es;
    for (register int i = 1; i <= os; ++i) for (register int j = 1; j <= es; ++j)
        if (!unPrime[odd[i] + even[j]]) edge[i].push_back(j); // 连边
    for (register int i = 1; i <= os; ++i) ans -= solve(i, i);
    cout << ans;
    return 0;
}

:::

这个代码用的是匈牙利，理论上是过不了的，但是用 C++23 就过了，不过这个还是没过，所以仅作参考，建议使用网络最大流算法。