글 읽기 - 틀린 부분을 못 찾겠습니다. 도와주세요! (주석 有)

pianop 2년 전 0

9% 정도에서 틀립니다.

트리의 꼭대기를 1로 고정하고 1 위에 있는 가상의 0, 0위의 가상의 N + 1 을 두었습니다. (재귀, 하향식)

시작 지점(now)은 0과 N+1으로 두번 탐색했고, 탐색 방식은 자신으로부터 거리2인 자녀(b)의 DP와 b의 자녀(c)들의 DP의 합 중 큰 값을 DP[now]+=형식으로 더해나갔습니다. 여기서 거리 2인 자녀의 DP가 컸다면 b를 now의 자녀벡터에 push_back해주었고 3인 자녀가 컸다면 그들 전부를 now의 자녀 벡터의 뒤에 그대로 붙여주는 식으로 탐색을 시켰습니다.

트리도 그려보고인터넷을 뒤지며 TC를 찾아도(전부 잘 됨) 무엇이 문제인지 못 찾겠어서 질문을 올려봅니다ㅠㅠ 도와주세요!

#include <iostream>
#include <vector>
#include <algorithm>
typedef std::vector<int > vi;
typedef std::vector<vi> vvi;

//재귀, DP 하향식
int FillDP(const int now, const int prev, const vvi& edges, const vi& cost, vi& DP, vvi& childrenbox)
{
	if (DP[now] != 0)				   	  //한 번 계산한 것이라면 그대로 반환
		return DP[now];

	DP[now] = cost[now];

	for (auto& a : edges[now])			  //거리 1인 자녀들(더할 수 없음)
	{
		if (a != prev)
		{
			for (auto& b : edges[a])            //거리 2 ,Max(b, b의 자녀(c)들의 합)을 DP[now]에 더해주기
			{
				if (b != now)
				{
					int tmp3 = 0;
					vi vtemp;    //거리 3이 답일 경우 now의 자녀로 편입시킬 임시 벡터(b의 거리1인 자녀들)
					for (auto& c : edges[b])    //거리 3 (2와 비교)
					{
						if (c != a)
						{
							vtemp.push_back(c);  
							tmp3 += FillDP(c, b, edges, cost, DP, childrenbox);  //(거리3) b의 자녀들인 DP[c]합치기
						}
					}

					int tmp2 = FillDP(b, a, edges, cost, DP, childrenbox); //DP[b]구해오기

					if (tmp2 > tmp3)
					{
						childrenbox[now].push_back(b);      //b 편입
						DP[now] += tmp2;
					}
					else
					{
						childrenbox[now].insert(childrenbox[now].end(), vtemp.begin(), vtemp.end()); // b의 자녀들 편입
						DP[now] += tmp3;
					}
				}
			}
		}
	}

	return DP[now];
}

void Tracing(int now, const vvi& childrenbox, vi& ansbox)
{
	for (auto& c : childrenbox[now])
	{
		ansbox.push_back(c);
		Tracing(c, childrenbox, ansbox);     //자녀들 그대로 따라가서 ansbox에 추가, 재귀
	}
}

int main()
{
	std::ios::sync_with_stdio(false); std::cin.tie(NULL); std::cout.tie(NULL);

	int N;
	std::cin >> N;

	vi cost(N + 2);
	for (int i = 1;i <= N;i++)
		std::cin >> cost[i];

	vvi edges(N + 2);
	for (int i = 1;i < N;i++)
	{
		int a, b;
		std::cin >> a >> b;
		edges[a].push_back(b);
		edges[b].push_back(a);
	}

	edges[0].push_back(1);          //1번으로 이어지는 가상의 0번 정점 추가
	edges[N + 1].push_back(0);      //0번으로 이어지는 가상의 N + 1번 정점 추가, N+1 -> 0 -> 1 -> edges[1]...
	vi DP(N + 2);
	vvi childrenbox(N + 2);
	int ans1 = FillDP(N + 1, -1, edges, cost, DP, childrenbox);  // DP채우기(N + 1 시작)
	int ans0 = FillDP(0, -1, edges, cost, DP, childrenbox);      // DP채우기(0 시작)

	int start = 0;
	vi ansbox;
	ansbox.reserve(N);
	if (ans1 > ans0)                 //0과 N+1중 어디서 시작한 것이 답인지 체크
	{
		start = N + 1;
		ans0 = ans1;
	}

	std::cout << ans0 << "\n";

	Tracing(start, childrenbox, ansbox);         //정답인 독립집합 ansbox에 채워넣기

	std::sort(ansbox.begin(), ansbox.end());
	for (auto& a : ansbox)
		std::cout << a << " ";

	return 0;
}

pianop 2년 전 2

반례 하나 찾았습니다..!

6
10 1 1 1 10 10
1 2
2 3
3 4
4 5
3 6

// Answer : 30
// Output : 21

1949 우수마을에서 역추적이 추가된 문제이니 다들 참고하시면 좋을 것 같아요!

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

문제

문제

출처

ICPC

틀린 부분을 못 찾겠습니다. 도와주세요! (주석 有)

pianop 2년 전 0

pianop 2년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말