题解 | #素数伴侣#

增广路算法不叙述了，实现看代码，很详细的

// https://www.nowcoder.com/practice/b9eae162e02f4f928eac37d7699b352e
#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;

const int maxn = 5 + 1e3;

int n;
int a[maxn];

int xsiz;  // 左部数量
vector<int> adj[maxn];

bool isPrime(int x) {
    for (int i = 2; i * i <= x; ++i)
        if (x % i == 0) return false;
    return true;
}

void init() {
    for (int j = 1; j <= n; ++j)  // 将集合划分为左右部，区别是奇偶性
        if (a[j] % 2) swap(a[++xsiz], a[j]);
    for (int u = 1; u <= xsiz; ++u) {
        for (int v = xsiz + 1; v <= n; ++v) {
            if (!isPrime(a[u] + a[v])) continue;  // 如果和为素数，那么添加二部图的边
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
    }
}

int match[maxn];  // match[u] = v
bool visit[maxn];

// 尝试找一条起点为 v 的增广路
bool dfs(int v) {
    if (visit[v]) return 0;
    visit[v] = 1;
    // 递归过程：通过虚边找到一条有实边的节点 u，然后递归处理 match[u]
    for (auto u : adj[v]) {
        if (match[u] == v) continue;    // 是一条实边
        if (match[u] == 0) continue;    // v 通过了虚边找到了 u，但是 u 没有实边
        if (visit[match[u]]) continue;  // u 的实边指向已搜索的 v
        if (dfs(match[u])) {
            // 找到了以 match[u] 为起点的增广路
            // 那么加上两条边仍是增广路：v-->u-->match[u]
            match[u] = v;  // 那么交换虚实边
            return true;
        }
    }

    // 尝试找一条虚边
    for (auto u : adj[v]) {
        if (match[u] == 0) {
            match[u] = v;
            return true;
        }
    }
    return false;  // 没找到
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    init();

    for (int v = xsiz + 1; v <= n; ++v) {
        memset(visit, 0, sizeof(visit));
        dfs(v);
    }

    int ans = 0;
    for (int u = 1; u <= xsiz; ++u)
        if (match[u]) ++ans;
    cout << ans;
}