글 읽기 - 소수 쌍 반례 ㅠㅠ

medic_programmer 7년 전 0

아무리 찾아도 못찾겠습니다 ㅠㅠ Backtracking 결과와도 다른 데이터가 없고 ㅠㅠ

혹시 이 문제에서 틀리기 쉬운 반례가 있나요??

#include<stdio.h>
#include<algorithm>

#define M 101

int d[M],graph[M][M],n,queue[M*M*M],from[M*M*M],front,rear,temp[M],data[M][M],answer[M],ap;
bool chk[M];

bool pcheck(int a)
{
	int i;
	for(i=2; i*i<=a; i++) if(a%i == 0) return false;
	return true;
}

int process()
{
	int i,get,cnt,ans=0;
	bool flag;

	
	while(1){
		front = rear = 0;
		queue[++front] = 0;
		from[front] = -1;
		
		for(i=0; i<=n+1; i++) chk[i] = false;
		chk[0] = 1;
		
		while(1){
			flag = false;
			if(rear >= front) break;
			get = queue[++rear];
			for(i=0; i<=n+1; i++){
				if(graph[get][i] != 0 && chk[i] == false){
					chk[i] = true;
					queue[++front] = i;
					from[front] = rear;
					if(i == n+1){
						flag = true;
						break;
					}
				}
			}
			
			if(flag == true) break;
		}
		
		if(flag == true){
			cnt = 0;
			while(1){
				temp[++cnt] = queue[front];
				front = from[front];
				if(front == -1) break;
			}
			for(i=2; i<=cnt; i++){
				graph[temp[i-1]][temp[i]]++;
				graph[temp[i]][temp[i-1]]--;
			}
			
			ans++;
		}
		
		else break;
		
	}
	
	return ans;
}

int main()
{
	int i,j,get,k,ans=0;
	//freopen("input.txt","r",stdin);
	
	scanf("%d",&n);
	for(i=1; i<=n; i++) scanf("%d",&d[i]);
	
	
	if(d[1] % 2 == 1){
		for(i=1; i<=n; i++){
			if(d[i]%2 == 1) graph[0][i] = 1;
			else graph[i][n+1] = 1;
		}
		for(i=1; i<=n; i++){
			if(d[i] % 2 == 0) continue;
			for(j=1; j<=n; j++){
				if(d[j] % 2 == 1) continue;
				if(pcheck(d[i]+d[j]) == 1) graph[i][j] = 1;
			}
		}
	}
	
	else{
		for(i=1; i<=n; i++){
			if(d[i]%2 == 0) graph[0][i] = 1;
			else graph[i][n+1] = 1;
		}
		for(i=1; i<=n; i++){
			if(d[i] % 2 == 1) continue;
			for(j=1; j<=n; j++){
				if(d[j] % 2 == 0) continue;
				if(pcheck(d[i]+d[j]) == 1) graph[i][j] = 1;
			}
		}
	}
	
	for(j=0; j<=n+1; j++) for(k=0; k<=n+1; k++)	data[j][k] = graph[j][k];
	
	for(i=2; i<=n; i++){
		
		if(graph[1][i] == 1){
			
			for(j=0; j<=n+1; j++) for(k=0; k<=n+1; k++)	graph[j][k] = data[j][k];
			
			graph[0][1] = 0;
			graph[1][i] = 0;
			graph[i][n+1] = 0;
			
			get = (process() + 1);

			if(get > ans){
				ans = get;
				ap = 0;
				answer[++ap] = d[i];
			}
			else if(get == ans) answer[++ap] = d[i];
		}
	}
	if(ap == 0) printf("-1\n");
	
	else{
		std::stable_sort(answer+1,answer+ap+1);
		for(i=1; i<=ap; i++) printf("%d ",answer[i]);
	}
	
	return 0;
}

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

문제

문제

출처

ICPC

소수 쌍 반례 ㅠㅠ

medic_programmer 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말