글 읽기 - 소수쌍 질문

sgc109 7년 전 0

우선 제가 짠 소스는 우선 입력값에서 모든 쌍을 대상으로 합이 소수인지 판별하여 소수이면 간선을 그었고

그다음에 이분그래프를 만들어야하는데 정확히 노드들이 두개의 컴포넌트로 분리되어야하지만

모든 경우에 이분그래프가 형성이 된다고 가정하고 그래프를 만들었다가 혹시라도 같은 컴포넌트끼리의 간선이 생기는 경우가 있다면

예상치못한 결과가 나올 수 있다고생각해서.. 우선 dfs 로 그래프를 2가지색으로 색칠(?) 을 하여 인접한 노드가 다른색을 가지도록 두가지색으로 구분하여

노드들사이의 모든 간선을 검사하여 만약 인접한 노드가 같은색을 가진다면 이분그래프를 만들수가 없으므로 바로 -1을 출력하고 종료하게했고

dfs를 한 노드에서만 돌려서 방문한 점의 개수를 세서 총 정점의 개수와 비교해서 만약 따로 떨어져있는 노드가있는지(어떤 수와 더하더라도 소수가 될수없는 수가 존재)를 판별해서 이런경우가 있어도 무조건 -1 을 출력하고 종료하게했습니다.

이 모든 과정을 거치고도 종료하지않았다면 색칠하기에서 색이 0이었던건 source 에서 그 점들로 나가는 간선을 그리고 (1번째점의 색이0)

색이 1이었던건 그 점들에서 sink 로 나가는 간선을 그리는 식으로 이분그래프를 형성하여

source -> 1번점 의 capacity 를 0으로 바꾸고 1번점과 연결된 수들을 for문 돌리며

1번점과연결된특정점 -> sink 의 capacity 를 0으로 바꿨다가 edmonds karp 알고리즘이 끝나면 다시 1로 바꿔주고 이런식으로하고

edmonds karp 가 종료한뒤엔 maxFlow 가 총 정점의 개수/2 -1 인지 판별합니다(1번째점은 for문을 돈다는거자체가 무조건 일단 짝이지어진것이니 1을 뺌)

맞다면 1번째점과 이 점을 짝지었을때 모두 짝을지을수있는것이므로 답에 추가합니다.

이런식으로 작성했는데.. 좀 많이 복잡하고 코드가 길어졌는데 애초에 맨앞에 2가지 색으로 색칠이 가능한지 확인을 할 필요가없는진잘모르겠지만 우선 예제 입력이랑 제가 만든 케이스에선 맞는답이 나왔는데 틀렸습니다. 가 나오는데 제 방식이 잘못된걸까요? 아니면 뭔가 실수한 부분이있는걸까요?

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <utility>
#include <stack>
#include <cstring>
#include <cstdlib>
#include <string>
#include <unordered_set>
#include <set>
#include <map>
#define REP(i,a,b) for(int i = a; i < b;++i) 
#define FOR(i,n) REP(i,0,n)
#define mp make_pair
#define pb push_back
#define inp1(a) scanf("%d",&a)
#define inp2(a,b) scanf("%d%d",&a,&b)
#define inp3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define inp4(a,b,c,d) scanf("%d%d%d%d",&a,&b,&c,&d)

using namespace std;

typedef pair<long long, long long> pll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;

const int INF = 0x3a3a3a3a;
const long long INFL = 0x3a3a3a3a3a3a3a3a;
const int MAX_N = 10000;
const int MAX_V = 52;

int notPrime[100000]={1,1,};
vi adj[MAX_V];
int cap[MAX_V][MAX_V], flow[MAX_V][MAX_V];
int n;
int a[MAX_V];

int visited[MAX_V];
int visitCnt;
int color[MAX_V];
bool dfs(int here) {
	bool colorable = true;
	FOR(i,adj[here].size()) {
		int there = adj[here][i];
		if(there == 0 || there == 1) continue;
		if(visited[there] == 0) {
			visited[there] = 1;
			color[there] = color[here]^1;
			if(color[there] == 0) {
				cap[color[there]][there]=1;
			}
			else if(color[there] == 1) {
				cap[there][color[there]]=1;
			}
			adj[color[there]].pb(there);
			adj[there].pb(color[there]);

			++visitCnt;
			if(!dfs(there)) return false;
		}
		else if(color[there] == color[here]) return colorable=false;
	}
	return colorable;
}

bool isColorable() {
	visitCnt=1;
	memset(color,-1,sizeof(color));
	visited[2] = 1;
	color[2] = 0;
	cap[0][2] = 1;
	adj[0].pb(2);
	adj[2].pb(0);

	if(!dfs(2)) return false;
}

int parent[MAX_V];
bool dfs2(int here) {
	if(here == 1) return true;
	FOR(i,adj[here].size()) {
		int there = adj[here][i];
		if(cap[here][there]-flow[here][there]>0 && parent[there] == -1) {
			parent[there] = here;
			if(dfs2(there)) return true;
		}
	}
	return false;
}

int edmonds() {
	int ret=0;
	while(true) {
		memset(parent,-1,sizeof(parent));
		parent[0] = 0;
		if(!dfs2(0)) break;
		int minFlow = INF;
		for(int p = 1; p != parent[p]; p = parent[p]) {
			minFlow = min(minFlow,cap[parent[p]][p]-flow[parent[p]][p]);
		}
		for(int p = 1; p != parent[p]; p = parent[p]) {
			flow[parent[p]][p] += minFlow;
			flow[p][parent[p]] -= minFlow;
		}
		ret+=minFlow;
	}
	return ret;
}

int main() {
	for(int i = 2; i * i <= 100000; ++i) {
		if(notPrime[i] == 0) {
			for(int j = 2*i; j < 100000; j+=i) {
				notPrime[j] = 1;
			}
		}
	}
	inp1(n);
	FOR(i,n) inp1(a[i]);
	sort(a,a+n);
	FOR(i,n) {
		REP(j,i+1,n) {
			if(!notPrime[a[i]+a[j]]) {
				adj[2+i].pb(2+j);
				adj[2+j].pb(2+i);
			}
		}
	}

	if(!isColorable()) {
		printf("-1");
		return 0;
	}
	if(visitCnt!=n) {
		printf("-1");
		return 0;
	}

	FOR(i,n) {
		REP(j,i+1,n) {
			if(!notPrime[a[i]+a[j]]) {
				if(color[2+i]==0) cap[2+i][2+j]=1;
				else cap[2+j][2+i]=1;
			}
		}
	}

	vi ans;

	cap[0][2]=0;
	FOR(i,adj[2].size()) {
		if(adj[2][i]==0) continue;
		memset(flow,0,sizeof(flow));
		cap[adj[2][i]][1]=0;
		int matched = edmonds();
		if((matched+1) == (n/2)) ans.pb(a[adj[2][i]-2]);

		cap[adj[2][i]][1]=1;
	}
	if(ans.size()==0) {
		printf("-1");
		return 0;
	}
	FOR(i,ans.size()) {
		printf("%d ",ans[i]);
	}
	
	return 0;
}

f52985 7년 전 0

a를 정렬한게 문제가 된 것 같네요. 첫번째 수라는 것은 정렬했을때 가장 작은 수가 아니라, 첫번째로 입력된 수를 의미합니다.

sgc109 7년 전 0

@f52985 아 감사합니다! 너무 허무하게 실수를 했네요.. 고쳐서 마지막에 답을 출력하기직전에 sort 하는걸로 바꿨는데 73% 에서 WA가 뜨네요..ㅠㅠ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

소수쌍 질문

sgc109 7년 전 0

f52985 7년 전 0

sgc109 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말