[1017] 소수 쌍

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

1017번: 소수 쌍

<문제>

에라토스테네스의 체를 사용해 bool isPrime[2001]을 채워준다.(전처리)

이분매칭을 사용하기 전에, input[i]+input[j]가 소수일때 i와 j를 양방향으로 연결해준다.

 

고전적인 이분매칭은 두개의 이분그래프에서 최대 몇개가 매칭되는지를 파악할 수 있는데,

입력되는 수열의 길이 n이 짝수이므로, n/2번 매칭되었을때 input[1]과 연결된 수를 찾아주면 된다.

input[1]를 모든 adj[1]에 대해서 연결시켜준다. 이것이 이분매칭을 시작하기 전의 초기상태이다.

이후엔, input[1], input[1]과 연결된 다른것 하나, 총 2개를 제외하고

(n-2)/2번 매칭이 되었다면, 정답의 조건을 충족한다고 판단할 수 있다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int n, p[1001];
vector<int> v;
vector<int> adj[1001];
bool isPrime[2001], s[1001], visited[1001];
bool f(int cur) {
    if (visited[cur] == true) return false;
    visited[cur] = true;
    for (auto& next : adj[cur]) {
        if (p[next] == 0 || f(p[next]) == true) {
            p[next] = cur;
            p[cur] = next;
            s[cur] = s[next] = true;
            visited[next] = true;
            return true;
        }
    }
    return false;
}
int main(void) {
    int i, j;
    cin >> n;
    v.resize(n + 1);
    for (i = 1; i <= n; i++) cin >> v[i];
    memset(isPrime, true, sizeof(isPrime));
    isPrime[0] = isPrime[1] = false;
    for (i = 2; i * i <= 2000; i++) {
        if (isPrime[i] == false) continue;
        for (j = i * 2; j <= 2000; j += i) isPrime[j] = false;
    }
    sort(v.begin() + 2, v.end());
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= n; j++) {
            if (i == j) continue;
            if (isPrime[v[i] + v[j]] == true) {
                adj[i].push_back(j);
            }
        }
    }
    vector<int> ans;
    for (auto& i : adj[1]) {
        memset(p, 0, sizeof(p));
        memset(s, 0, sizeof(s));
        int cnt = 2, temp = i;
        for (j = 1; j <= n; j++) {
            if (s[j] == true) continue;
            memset(visited, 0, sizeof(visited));
            visited[1] = visited[temp] = true;
            p[1] = temp;
            p[temp] = 1;
            s[1] = s[temp] = true;
            if (f(j) == true) {
                cnt += 2;
            }
        }
        if (cnt == n) {
            ans.push_back(i);
        }
    }
    if (ans.empty()) {
        cout << "-1";
        return 0;
    }
    for (auto& i : ans) cout << v[i] << " ";
 
    return 0;
}