글 읽기 - 사람한명 살려주십시오

Viento 4년 전 0

이분 매칭 공부하려고 시도해봤고

내용이 기니 함수별로 요약해서 설명드리면

era_init으로 소수 필드 만들어놓고

입력받은건 배열에 저장한다음

간선을 1~n 번째 수를 홀수 -> 짝수중 합이 소수가 되는 짝으로 만들어줬습니다.

이유는

홀수 + 짝수만 소수가 될 수 있어서
0은 i번째 수랑 고정되서 소수짝 매칭에 포함 안할거니까

입니다. 그리고 1~n-1 루프를 돌면서

arr[0] + arr[i] 가 소수가 되는 Primary 를 찾아 저장 후

더티(visited) 배열이랑 connected 배열 초기화하고

bmatch함수를 실행해서 (Primary가 아님 && 홀수) 일 때 dfs를 실행하고

dfs는 index 번째 배열의 값을 연결할 수 있는 짝을 찾는 탐색입니다. 더티배열로 순환 못하게 체크하고

간선 순회중 (connected가 -1임[연결 안되있음] || dfs(connected[e] 가 true(연결된 대상이 다른 대상과 연결가능함))

일 때 connected 갱신 후 true 를 반환합니다. 갈 수 있는 모든 간선을 순회 후 true가 나오지 않는다면 false를 반환하구여.

새로운 연결은 단 한번만 해주는 dfs이기 때문에(변경은 기존에 카운트된 연결) 성공 시마다 1씩 더해주구여.

이 총계가 n/2일 경우 참으로 보고 Primary를 출력합니다. nans 로 카운트해서 참없으면 -1 출력이구여.

맞았습니다 뜨는 상상했는데 어림도없지 8시간동안 삽질중입니다 제발 저좀 살려주십시오

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
namespace PS
{
	using namespace std;


	const int eraLen = 3000;
	bool eratos[eraLen];

	void era_init()
	{
		for (int i = 0; i < eraLen; i++)
			eratos[i] = false;
		eratos[0] = true;
		eratos[1] = true;
		for (int i = 0; i < eraLen; i++)
		{
			if (!eratos[i])
			{
				for (int j = i + i; j < eraLen; j += i)
				{
					eratos[j] = true;
				}
			}
		}
	}

	int n;
	int arr[50];
	bool dirties[50] = { 0 };
	int connected[50] = { 0 };
	int primary;
	vector<int> edges[50];

	bool dfs(int index)
	{
		//cout << "d" << arr[index] << "\n";
		if (dirties[index]) return 0;
		dirties[index] = true;
		for (auto e : edges[index])
		{
			if (e == primary)
				continue;
			//cout << arr[index] << "=>" << arr[e] << "\n";
			if (connected[e] == -1 || dfs(connected[e]))
			{
				//cout << arr[index] << "&" << arr[e] << "\n";
				connected[e] = index;
				dirties[index] = false;
				return true;
			}
		}
		dirties[index] = false;
		return false;
	}

	int bmatch()
	{
		int l = 0;
		//cout << "P" << arr[primary] << "\n";
		for (int j = 1; j < n; j++)
		{
			if (j == primary)
				continue;
			if (arr[j] % 2 == 0)
				continue;
			//cout << j <<"["<<arr[j]<<"]" << "\n";
			if (dfs(j))
				l++;
		}
		return l;
	}

	void solve()
	{

		// eratos_init
		era_init();

		// input_accept
		
		cin >> n;
		//n = 50;
		for (int i = 0; i < n; i++)
		{
			cin >> arr[i];
		}

		sort(&arr[1], &arr[n - 1]);
		for (int i = 1; i < n; i++)
		{
			if(arr[i] %2 == 1)		
				for (int j = 1; j < n; j++)
				{
					if (arr[j] % 2 == 0 && !eratos[arr[i] + arr[j]])
					{
						edges[i].push_back(j);
						//cout << arr[i] << "->" << arr[j] << "\n";
					}
				}
		}
		int nans = 0;

		for (int i = 1; i < n; i++)
		{
			if (eratos[arr[0] + arr[i]])
				continue;
			for (int i = 0; i < 50; i++)
			{
				connected[i] = -1;
				dirties[i] = false;
			}
			primary = i;
			int ans = bmatch()+1;
			if (ans == n / 2)
			{
				nans++;
				cout << arr[i] << " ";
			}
		}
		
		if (nans == 0)
			cout << -1 << " ";
	}
}

int main()
{
	PS::solve();
	return 0;
}

kcm1700 4년 전 3

일단 답을 오름차순 정렬해서 출력해야 하는 게 빠졌네요.

kcm1700 4년 전 1

40
153 801 88 61 927 11 758 171 316 577 228 44 759 165 110 883 87 566 488 578 475 626 628 630 929 424 521 903 963 124 597 738 262 196 526 265 261 203 117 31

그리고 이거 넣었더니 안 끝나네요.

Viento 4년 전 0

울트라 캡숑 고수님이 알려주신 반례로 해결했습니다.

제가 visited 를 이상한 시점에서 풀어 제기능을 못했네요.

Viento 4년 전 0

근데 아직 궁금한 게 하나가 있는데요.

왜 dfs가 실패하면 실패인거로 풀면 틀리고

dfs가 성공시마다 1씩 더해서 링크 총계가 n/2 인 것으로 하면 맞을까요?

i번째에 dfs 를 성공하면 다른 노드의 점유를 빼앗든, 아니면 새로운 점유를 얻든 해서 짝을 찾은 것 아닌가요?

그러니까 결국 모든 dfs가 성공해야 모든 노드가 짝을 찾아 n/2개의 연결이 생기는게 아닌가 라고 생각했는데..

혹시 이걸 아시는 분은 답변을 달아주시면 3대가 행복하고 하는 일이 다 잘 되실겁니다.

mozzi01331 4년 전 0

제 추측이지만.. a와 b의 개수가 일치하지 않을때 (ex. a 2개 b 4개) a에 대한 dfs 탐색이 모두 성공해도 '모든 수'가 매칭된 게 아니기 때문 아닐까요?

Viento 4년 전 0

아 그러네요 이분 매칭으로 홀수 -> 짝수로 찾으니 잉여 짝수가 생기는 경우에는 탐색은 전부 성공하지만

실제 문제에서 찾아야하는 모든 소수쌍 조건엔 맞지않네요

찾아주셔서 감사합니다.

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

문제

문제

출처

ICPC

사람한명 살려주십시오

Viento 4년 전 0

kcm1700 4년 전 3

kcm1700 4년 전 1

Viento 4년 전 0

Viento 4년 전 0

mozzi01331 4년 전 0

Viento 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말