글 읽기 - 소수 쌍 98%에서 런타임 에러가 뜹니다..

clifter0122 6년 전 0

알고리즘은 먼저 1과 어떤 수를 matching 해준 뒤, 각 숫자들을 홀수 짝수로 나누어 Hopcroft-Karp 알고리즘으로 이분매칭하여 최대 matching이 n/2인 경우 1과 그 수가 서로 더해질 수 있음을 의미하므로 출력되도록 하였습니다. 이상하게 98%만 진행되면 자꾸 런타임 에러가 뜨네요.. 아래에 소스코드 첨부합니다.

#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
vector<int> graph[51];
queue<int> Q;
int a[51],dist[51],chk[51],pre[51],p[2001],primecheck[2001],ANS[2000];
int dfs(int x){
	for(int i=0;i<graph[x].size();i++){
			if(pre[graph[x][i]]==0||(dist[pre[graph[x][i]]]==dist[x]+1&&dfs(pre[graph[x][i]])==1)){
				chk[x]=1;
				pre[graph[x][i]]=x;
				return 1;
			}	
	}
	dist[x]=987654321;
	return 0;
}
int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	p[1]=2;
	primecheck[2]=1;
	int primenum=1;
	for(int i=3;i<=2000;i++){
		int c=0;
		for(int j=1;p[j]*p[j]<=i;j++){
			if(i%p[j]==0) c++;
		}
		if(c==0){
			primenum++;
			p[primenum]=i;
			primecheck[i]=1;
		}
	}
	for(int t=2;t<=n;t++)
	{
		int onematch, match=0;
		if(primecheck[a[1]+a[t]]==1){
		onematch=t;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(primecheck[a[i]+a[j]]==1&&i!=1&&i!=onematch&&j!=1&&j!=onematch&&i!=j){
					graph[i].push_back(j);
					graph[j].push_back(i);
				}
			}
		}
		while(1){
		int counter=0;
			for(int i=1;i<=n;i++){
				if(a[i]%2==0&&chk[i]==0) {
					dist[i]=0; Q.push(i);
				}
				else{
					dist[i]=987654321;
				}
			}
			while(!Q.empty()){
				int t=Q.front();
				Q.pop();
				for(int i=0;i<graph[t].size();i++){
					if(dist[pre[graph[t][i]]]==987654321){
						dist[pre[graph[t][i]]]=dist[t]+1;
						Q.push(pre[graph[t][i]]);
					}
				}
			}
			for(int i=1;i<=n;i++){
				if(a[i]%2==0&&chk[i]==0&&dfs(i)==1) counter++;
			}
			if(counter==0) break;
			else match+=counter;
			}
		}
		if(match==n/2-1) ANS[a[onematch]]++;
		for(int i=1;i<=n;i++){
			chk[i]=0; dist[i]=0; pre[i]=0; graph[i].clear();
		}
	}
	int zerocheck=0;
	for(int i=1;i<=1000;i++){
		if(ANS[i]>0) {
		zerocheck++; printf("%d ",i);
		}
	}
	if(zerocheck==0) printf("-1");
}

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

문제

문제

출처

ICPC

소수 쌍 98%에서 런타임 에러가 뜹니다..

clifter0122 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말