글 읽기 - 2197 분해반응 질문입니다.

kinssang 5년 전 0

전체 트리의 root를 1번 node로 두고,
dp[i][j] = i번 node를 root로 하는 subtree에서 j개 만큼의 원소를 제거할 때 최소한으로 필요한 간선 제거 횟수.
value[i] = i번 node를 root로 하는 subtree의 원소의 갯수(크기)
로 dp를 구한 다음, 답의 경우는 i가 전체 트리의 root인 경우와, i가 전체 트리의 root가 아닌 경우로 나누어서,
i가 root인 경우는 dp[i][N-M],
i가 root가 아닌 경우는 전체 트리에서 서브트리로 떨어져 나오는데 간선 제거를 한번 했으므로, 1+dp[i][value[i]-M]
으로 생각해서 이 중 최소값을 구하는 식으로 답을 정했는데요.
시작하자마자 계속 틀렸습니다가 뜹니다. 혹시 반례를 얻을 수 있을까요?

#include <stdio.h>
#include <vector>

#define INF 987654321

int N, M, dp[151][151], value[151], ans = INF;
std::vector<int> adj[151];

int inline mn(int a, int b)
{
	return (a < b) ? a : b;
}

int dfs(int here, int parent)
{
	if (adj[here].size() != 1)
	{
		for (int i = 0; i < adj[here].size(); i++)
		{
			int there = adj[here][i];
			if (there == parent) continue;
			value[here] += dfs(there, here);
			int new_dp[151];
			for (int j = 0; j <= value[here]; j++) new_dp[j] = dp[here][j];
			for (int j = 0; j <= value[here] - value[there]; j++)
			{
				for (int k = 1; k <= value[there]; k++) new_dp[j + k] = mn(new_dp[j + k], dp[there][k] + dp[here][j]);
			}
			for (int j = 0; j <= value[here]; j++) dp[here][j] = new_dp[j];
		}
	}
	dp[here][value[here]] = 1;
	if (value[here] >= M) ans = mn(ans, dp[here][value[here] - M] + (here != 1));
	return value[here];
}

int main()
{
	freopen("input.txt", "r", stdin);
	scanf("%d %d", &N, &M);
	for (int i = 0, A, B; i < N - 1; i++)
	{
		scanf("%d %d", &A, &B);
		adj[A].push_back(B);
		adj[B].push_back(A);
	}
	for (int i = 1; i <= N; i++)
	{
		value[i] = 1;
		for (int j = 1; j <= N; j++) dp[i][j] = INF;
	}
	dfs(1, 0);
	printf("%d\n", ans);
	return 0;
}

kinssang 5년 전 0

dfs를 애초에 잘못짜서 일자형 같은 경우에는 제대로 계산이 안됐었습니다. 해결했습니다

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

문제

문제

출처

ICPC

2197 분해반응 질문입니다.

kinssang 5년 전 0

kinssang 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말