글 읽기 - 1017 - 소수쌍 - 이분매칭 문제 질문드립니다... (인접 리스트 표현 사용)

wasa 4년 전 0

kks님의 풀이를 보고 짜고 있었습니다. 그러나 제 풀이는

인접 리스트 표현법을 쓰는데,

adj[ i ]를 리스트에 있는 i번쨰 홀수가 아니라,

그냥 수 i로 하고 접근하였습니다. (메모리 많이 먹는 접근)

그러나 통과되지 못하고 있습니다..

도와주세요 ㅜ.ㅜ 이제는 눈이 흐려지도록 모니터를 봐도 문제점을 찾지 못하였습니다...

어떤 부분이 문제가 있는지 궁금합니다.

감사합니다.

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> adj[1001], A, B;
vector<bool> vis;
int n;
int arr[1001];
bool isPrime[3000];
int primes[1000];

int pSize = 0;

void genPrimes() {
	primes[pSize++] = 2;
	primes[pSize++] = 3;
	for (int n = 5; n <= 2000; n += 2) {
		bool flag = true;
		for (int i = 1; primes[i] * primes[i] <= n; ++i)
			if (n % primes[i] == 0) {
				flag = false;
				break;
			}
		if (flag)
			primes[pSize++] = n, isPrime[n] = true;
	}
}

bool dfs(int a) {
	if (vis[a]) return false;
	vis[a] = true;
	for (int b : adj[a]) {
		if (B[b] == -1 || dfs(B[b])) {
			A[a] = b;
			B[b] = a;
			return true;
		}
	}
	return false;
}

int main() {
	genPrimes();
	scanf("%d", &n);
	int complete = 0;
    //카운팅 소트와 비슷하게 원소가 리스트에 있다는 것을 arr에 저장
	for (int i = 0; i < n; ++i) {
		int x;
		scanf("%d", &x);
		arr[x] = true;
        //홀수 원소의 갯수를 센다
		if (x & 1) ++complete;
	}

    //애초에 불가능
	if (complete * 2 != n) {
		puts("-1");
		return 0;
	}

    //간선 만들어주기
	for (int i = 1; i <= 1000; i += 2)
		for (int j = 2; j <= 1000; j += 2)
			if (arr[i] && arr[j] && isPrime[i + j])
				adj[i].push_back(j);

    //가장 작은 홀수 원소 찾기
	int start;
	for (int i = 1; i <= 1000; i += 2)
		if (arr[i]) {
			start = i;
			break;
		}

	vector<int> ans;
	for (int b : adj[start]) {
		A = vector<int>(1001, -1);
		B = vector<int>(1001, -1);
		int cnt = 1;
		A[start] = b;
		B[b] = start;
		for (int i = start + 2; i <= 1000; i += 2) {
			if (arr[i] == false) continue;
			vis = vector<bool>(1001);
			vis[start] = true;
			if (dfs(i)) ++cnt;
		}
		if (cnt == complete) ans.push_back(A[start]);
	}

	if (ans.empty())
		puts("-1");
	else {
		sort(ans.begin(), ans.end());
		for (int i : ans)
			printf("%d ", i);
	}
    return 0;
}

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

문제

문제

출처

ICPC

1017 - 소수쌍 - 이분매칭 문제 질문드립니다... (인접 리스트 표현 사용)

wasa 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말