1017번 : 소수 쌍

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

1017번: 소수 쌍

집합에 속한 임의의 원소 두개의 합이 소수가 되도록 모두 짝지었을 때 첫 번째 원소와 짝지은 원소들을 오름차순으로 출력하는 문제다.

아이디어, 구현 : 

네트워크 플로우(이분매칭)으로 해결할 수 있었다. 하지만 조금 특이한 방식으로 해결했다.

먼저, 모든 수를 두개로 늘려서 짝지을 첫번째 원소, 짝지을 두번째 원소로 나누었다. 첫 번째 원소는 제외하고.
즉 첫 번째 그룹에는 N-1개, 두번째 그룹에도 똑같이 N-1개가 있고, src에서 첫 번째 그룹으로, 첫 번째 그룹에서 두 번째 그룹으로, 두 번째 그룹에서 snk로 가도록 이분매칭 형태를 만들었다.

어떤 수 a와 어떤 수 b의 합이 소수일 때 첫번째 그룹에서 두번째그룹으로 가는 간선을 추가해주었다. 소수 판정을 에라토스테네스의 체와 이분탐색으로 해결했다. (지금 생각해보니 에라토스테네스의 체에서 바로 소수판정을 해도 괜찮을 것 같다.) 아무튼 간선을 다 추가한 다음, src->첫번째그룹에 있는 첫번째 수 -> 두번째그룹에 있는 다른 수->snk 이런 경로를 하나씩 추가한 후 max flow를 돌려서 N-1이 나오면 답으로 추가했다.

상어의 저녁식사 [https://www.acmicpc.net/problem/1671] 문제랑 동일하게 해결했다.

 

다른 분들은 짝수그룹, 홀수그룹으로 나눠서 dfs를 돌렸다. 그것도 좋은 방법인 것 같다.

코드 : 

#include <bits/stdc++.h>
using namespace std;
const int MN=50;
const int INF=987654321;
int arr[MN];
vector<int> G[MN*2+2];
int c[MN*2+2][MN*2+2], f[MN*2+2][MN*2+2], p[MN*2+2];
vector<int> prime;
int sieve[3000];
void init(){
	for(int i=0; i<MN*2+2; ++i){
		for(int j=0; j<MN*2+2; ++j){
			f[i][j]=0;
		}
	}
}
int maxFlow(int src, int snk){
	int ret=0;
	while(1){
		fill(p, p+MN*2+2, -1); p[src]=src;
		queue<int> q; q.push(src);
		while(!q.empty() && p[snk]==-1){
			int cur=q.front(); q.pop();
			for(auto nxt:G[cur]){
				if(c[cur][nxt]-f[cur][nxt]>0 && p[nxt]==-1){
					q.push(nxt);
					p[nxt]=cur;
				}
			}
		}
		if(p[snk]==-1) break;
		int flow=INF;
		for(int i=snk; i!=src; i=p[i]){
			flow=min(flow, c[p[i]][i]-f[p[i]][i]);
		}
		for(int i=snk; i!=src; i=p[i]){
			f[p[i]][i]+=flow;
			f[i][p[i]]-=flow;
		}
		ret+=flow;
	}
	return ret;
}
int main(){
	int N; cin>>N;
	for(int i=0; i<N; ++i){
		cin>>arr[i];
	}
	for(int i=2; i*i<3000; ++i){
		if(sieve[i]) continue;
		for(int j=i*i; j<3000; j+=i){
			sieve[j]=1;
		}
	}
	for(int i=2; i<3000; ++i){
		if(!sieve[i]) prime.push_back(i);
	}
	int src=MN*2, snk=MN*2+1;
	for(int i=1; i<N; ++i){
		G[src].push_back(i);
		G[i].push_back(src);
		c[src][i]=1;

		G[i+MN].push_back(snk);
		G[snk].push_back(i+MN);
		c[i+MN][snk]=1;
		for(int j=1; j<N; ++j){
			if(i==j) continue;
			if(binary_search(prime.begin(), prime.end(), arr[i]+arr[j])){
				// cout << arr[i] << ", " << arr[j] << '\n';
				G[i].push_back(j+MN);
				G[j+MN].push_back(i);
				c[i][j+MN]=1;
			}
		}
	}
	G[src].push_back(0);
	G[0].push_back(src);
	c[src][0]=1;
	vector<int> res;
	for(int i=1; i<N; ++i){
		G[0].push_back(i+MN);
		G[i+MN].push_back(0);
		if(binary_search(prime.begin(), prime.end(), arr[0]+arr[i])){
			c[0][i+MN]=1;
			init();
			int temp=maxFlow(src,snk);
			// cout << "i : " << i << ", temp : " << temp << '\n';
			if(temp==N-1){
				res.push_back(arr[i]);
			}
			c[0][i+MN]=0;
		}
	}
	if(res.size()==0) cout << "-1\n";
	else{
		sort(res.begin(), res.end());
		for(auto it:res) cout << it << ' ';
		cout << '\n';
	}
}