백준1017 소수 쌍

작성일 | In

문제 링크

  • http://icpc.me/1017

사용 알고리즘

  • 네트워크 플로우
  • 최대 유량
  • 이분 매칭

풀이

2를 제외한 소수는 모두 홀수이고, 주어지는 수에는 중복이 없습니다.
그러므로 두 수의 합으로 만들 수 있는 소수는 모두 홀수입니다.

입력으로 들어오는 숫자들을 홀수와 짝수로 분류한 뒤, 더하면 소수가 되는 쌍들을 간선으로 이어주면 이분 그래프가 나옵니다.
모든 수를 짝짓는다는 것은 홀수 그룹과 짝수 그룹의 크기가 같고, 매칭 개수도 같다는 것을 의미합니다.

첫 번째 수와 매칭할 수 있는 모든 수를 찾아주는 것은 첫 번째 수와 다른 그룹의 어떤 수를 미리 매칭시킨 뒤, 이분 매칭을 돌리는 것을 반복하면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <bits/stdc++.h>
using namespace std;

int n;
int isP[2020];
int par[2020];
int chk[2020];
vector<int> ans, a, b;
vector<int> g[2020];
int bias=50;

bool flag = 0;

int fixA, fixB;

void era(){
	for(int i=2; i<2020; i++) isP[i] = 1;
	for(int i=1; i<2020; i++){
		if(!isP[i]) continue;
		for(int j=i+i; j<2020; j+=i) isP[j] = 0;
	}
}

bool dfs(int v){
	for(auto i : g[v]){
		if(chk[i]) continue;
		if(i == fixA || i == fixB) continue;
		chk[i] = 1;
		if(!isP[a[v] + b[i-bias]]) continue;
		if(par[i] == -1 || dfs(par[i])){
			par[i] = v; return 1;
		}
	}
	return 0;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	era();
	cin >> n;
	for(int i=1; i<=n; i++){
		int t; cin >> t;
		if(i == 1 && t%2 == 0) flag = 1;
		if(t & 1) a.push_back(t);
		else b.push_back(t);
	}
	if(a.size() != b.size()){
		cout << -1; return 0;
	}

	if(flag) swap(a, b);

	for(int i=0; i<a.size(); i++){
		for(int j=0; j<b.size(); j++){
			if(isP[a[i] + b[j]]) g[i].push_back(j+bias);
		}
	}

	for(int pre=0; pre<b.size(); pre++){
		memset(par, -1, sizeof par);
		if(!isP[a[0] + b[pre]]) continue;
		int match = 1;
		par[pre+bias] = 0;
		fixA = 0, fixB = pre+bias;

		for(int i=1; i<a.size(); i++){
			memset(chk, 0, sizeof chk);
			chk[0] = chk[pre+bias] = 1;
			match += dfs(i);
		}

		if(match != b.size()) continue;
		ans.push_back(b[pre]);
	}
	if(ans.size()){
		sort(ans.begin(), ans.end());
		for(auto i : ans) cout << i << " ";
	}else cout << -1;
}