题解 | #素数伴侣#

#include <cmath>
#include <iostream>
#include <iterator>
#include <vector>
#include "bits/stdc++.h"
using namespace std;

bool nodiv(uint64_t num, std::unordered_set<int>& divnt) {
    if (divnt.count(num)) {
        return true;
    }
    const int a = sqrt(num);
    bool is_true = true;
    for (int i = 2; i <= a; ++i) {
        if (!(num % i)) {
            return false;
        }
    }
    divnt.insert(num);
    return is_true;
}

enum class color {
    white,
    gray,
    black
};
struct vertex {
    //parent
    int p = -1;
    //color
    color c = color::white;
    //distance
    int d = 0;
};

struct fc {
    int f = -1;
    int c = -1;
    int cfp = std::numeric_limits<int>::max();
};

std::vector<vertex> bfs(std::vector<std::vector<fc>>& graph, int s, int t) {
    std::vector<vertex> hoge(graph.size());
    hoge[s].c = color::gray;
    std::queue<int> queue;
    queue.push(s);
    while (!queue.empty()) {
        const auto u = queue.front();
        queue.pop();
        for (int i = 0; i < graph.size(); ++i) {
            auto new_c_uv = 0;
            if (graph[u][i].c > 0 && graph[u][i].f >= 0) {
                new_c_uv = graph[u][i].c - graph[u][i].f;
            } else if (graph[i][u].c > 0 && graph[i][u].f >= 0) {
                new_c_uv = graph[i][u].f;
            }
            graph[u][i].cfp = new_c_uv;
            if (new_c_uv > 0 && hoge[i].c == color::white) {
                hoge[i].c = color::gray;
                hoge[i].d = hoge[u].d + 1;
                hoge[i].p = u;
                queue.push(i);
            }
        }
        hoge[u].c = color::black;
    }
    return hoge;
}

int max_prime_number(std::vector<std::vector<fc>>& graph, int s, int t) {
    int v;

    for (int i = 0; i < graph.size(); ++i) {
        for (int j = 0; j < graph[i].size(); ++j) {
            if (graph[i][j].c > 0) {
                graph[i][j].f = 0;
            }
        }
    }

    int sum = 0;
    while (true) {
        auto cp = std::numeric_limits<int>::max();
        auto cc = bfs(graph, s, t);
        int i1 = t;
        std::vector<std::pair<int, int>> edges;
        while (cc[i1].p >= 0) {
            int u = cc[i1].p;
            cp = std::min(cp, graph[u][i1].cfp);
            edges.push_back({u, i1});
            i1 = u;

        }
        if (i1 != 0) {
            int a = 0;
            std::vector<std::pair<int, int>> av ;
            for (int i = 1; i < graph.size() - 1; ++i) {
                for (int j = 1; j < graph[i].size() - 1; ++j) {
                    if (graph[i][j].c == 1 && graph[i][j].f == 1) {
                        a += graph[i][j].f;
                        av.push_back({i, j});
                    }
                }
            }
            break;
        }
        for (auto&& [u, v] : edges) {
            if (graph[u][v].c >= 0 && graph[u][v].f >= 0 ) {
                graph[u][v].f = graph[u][v].f + cp;
            } else {
                graph[v][u].f = graph[v][u].f - cp;
            }
        }
        sum += cp;
    }
    return sum;

}

int main() {
    int a = 0;
    std::unordered_set<int> divnt;

    while (std::cin >> a) {
        // 注意 while 处理多个 case
        std::unordered_map<int, int> odd;
        std::unordered_map<int, int> even;
        for (int i = 1; i <= a; ++i) {
            int b;
            std::cin >> b;
            if (b % 2) {
                odd[i] = b;
            } else {
                even[i] = b;
            }
        }
        int sum = 0;
        std::vector<std::vector<fc>> graph(a + 2, std::vector<fc>(a + 2, fc{}));
        for (auto&& [key, value] : odd) {
            for (auto&& [key2, value2] : even) {
                if (nodiv(value + value2, divnt)) {
                    graph[key][key2].c = 1;
                    ++sum;
                }
            }
        }
        //s->odd
        for (std::pair<int, int> value : odd ) {
            graph[0][value.first].c = 1;
        }
        //even->t
        for (std::pair<int, int> value : even) {
            graph[value.first][a + 1].c = 1;
        }
        std::cout << max_prime_number(graph, 0, a + 1) << std::endl;
    }
}
// 64 位输出请用 printf("%lld")

压根不会，翻书才做出来了，用的ford-fulkerson algorithm 照着算法导论实现的