1017번: 소수 쌍

https://www.acmicpc.net/problem/1017

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int n, rev[50];
bool ck[50];
vector<int> adj[50], v[2], res;
bool dfs(int h) {
    if (ck[h]) return false;
    ck[h] = true;
    for (auto t : adj[h]) {
        if (rev[t] == -1 || dfs(rev[t])) {
            rev[t] = h;
            return true;
        }
    }
    return false;
}
int main() {
    scanf("%d", &n);
    int p;
    for (int i = 0; i < n; i++) {
        int a;
        scanf("%d", &a);
        v[a % 2].push_back(a);
        if (!i) p = a % 2;
    }
    if (p) swap(v[0], v[1]);
    for (int i = 0; i < v[0].size(); i++) {
        for (int j = 0; j < v[1].size(); j++) {
            int k, s = v[0][i] + v[1][j];
            for (k = 2; k*k <= s; k++)
                if (s%k == 0) break;
            if (k*k > s) adj[i].push_back(j);
        }
    }
    for (auto it : adj[0]) {
        fill(rev, rev + v[1].size(), -1);
        rev[it] = 0;
        int cnt = 1;
        for (int i = 1; i < v[0].size(); i++) {
            fill(ck, ck + v[0].size(), false);
            ck[0] = true;
            if (dfs(i)) cnt++;
        }
        if (cnt == n / 2) res.push_back(v[1][it]);
    }
    sort(res.begin(), res.end());
    if (res.empty()) puts("-1");
    else for (auto it : res)
        printf("%d ", it);
    return 0;
}