글 읽기 - [힌트] 정말 안풀리시는 분들 참고하세요

helios789789 3년 전 9

그래프 (트리) DP 에서 유사한 문제는 많이 보셨을 거라고 생각됩니다.

독립 집합의 합을 구하는 것은 쉬우니 독립 집합에 속해있는 정점들을 구하는 부분에 대한 힌트입니다.

트리를 DFS로 순회할때, 현재 정점을 최대 독립 집합에 속하는 정점이라고 판단할 수 있는 기준은 다음과 같습니다.

1. DFS 순회 순서 상 에서 바로 전에 방문된 정점이 최대 독립 집합에 속하지 않음

2. cache[here][true] > cache[here][false] // 현재 집합을 독립집합에 포함하는것 이 포함하지 않는 경우보다 더 큰 독립 집합을 얻을 수 있음

2번 조건만 포함해서 최대 독립 집합에 속하는 정점을 구하니 틀리다고 나오고, 독립집합의 정의대로 1번 조건을 추가시켜주니 통과했네요

#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <climits>
#include <cstdio>
using namespace std;
#pragma warning(disable:4996)
typedef long long ll;

vector<int> adj[10001];
int cost[10001];
int cache[10001][2];
int num;


int dp(int here, int selected, int prev) {
	int& ret = cache[here][selected];
	if (ret != -1)
		return ret;

	if (selected) {
		ret = cost[here];
		for (auto& there : adj[here]) {
			if (there != prev)
				ret += dp(there, false, here);
		}
	}
	else {
		ret = 0;
		for (auto& there : adj[here]) {
			if (there != prev) {
				int cand1 = dp(there, true, here);
				int cand2 = dp(there, false, here);

				ret += max(cand1, cand2);
			}
		}
	}
	return ret;
}
vector<int> paths;
bool seen[10001];

void dfs(int here, int prev) {
	if (cache[here][true] > cache[here][false] && seen[prev] == false) {
		paths.push_back(here);
		seen[here] = true;
	}

	for (auto& there : adj[here]) {
		if (there != prev) {
			dfs(there, here);
		}			
	}
}

int main() {
	cin >> num;
	for (int i = 1; i <= num; i++) {
		scanf("%d", &cost[i]);
	}
	int start, end;
	for (int i = 1; i < num; i++) {
		scanf("%d %d", &start, &end);
		adj[start].push_back(end);
		adj[end].push_back(start);
	}

	memset(cache, -1, sizeof(cache));
	int ret = dp(start, false, -1);
	ret = max(ret, dp(start, true, -1));
	cout << ret << endl;

	dfs(start, 0);

	sort(paths.begin(), paths.end());
	for (auto& path : paths)
		cout << path << " ";
	cout << endl;



	return 0;
}

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

문제

문제

출처

ICPC

[힌트] 정말 안풀리시는 분들 참고하세요

helios789789 3년 전 9

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말