1018

From BluWiki

A binnary Apple Tree условие

Возможное решение

Видно, что задачу можно решить перебором. Один из возможных вариантов, это начиная с корня заносить в массив доступные вершины(ветки) дерева, далее для каждой рекурсивно вызыввать эту функцию. Условие для прекращения, ограниченния глубины реккурсии будет число Q, т.е. количество веток которое нужно сохранить. Функция может выглядить так:

long int calculateMaxPreserveApples(
	list<TNode &> availableBranches,
	int branchesToPreserve,
	long int currentAmountOfPreservedApples
			);

Такое решение уже может работать! Очевидно что при Q > [N/2], лучше не считать максимальное кол-во яблок которые нужно оставить, а просчитать те ветки которые надо срубить(потому что их меньше по кол-ву). Увы, пока я не придумал достойного решения которое бы решало такую задачу. Возникли следующие недостатки:

• Т.к. ветки нужно срубать не с корня, а только те которые висят (не имеют сыновей), то по другому надо реализовывать инициализацию алгоритма.
• нужно заводить допоолнительный указатель на отца.
• Но лишь введение указателя не решает проблему, т.к. не все ветки помещенные в массив старым образом, являются правильными. Так нельзя рубить ветку, если она имеет хоть одного сына. Т.е. нужны дополнительные проверки.

Указанные недостатки наводят на мысль, пожертвовать случаями Q > [N/2] и пропускать их через обычный алгоритм.

Возможное еще усовершенствование, при котором будет считаться вес вестки(т.е. кол-во яблок на ней + яблоки на всех ветках-сыновьях).

Новое решение
Для вычислений резервируется таблица T размерности N*N. В T[i,1] записываются числа соответсвующие кол-ву яблок на ветке. Чтобы решить задачу по сохранению максимального количества яблок для любой ветки, можно записать следующее соотношение:

T[i, K] = T[i, 1] + max{j=0..K - 1} (T[i->left, K-j-1] + T[i->right, j]), где K - кол-во веток которые нужно сохранить (считая и i-ю)

Таким образом задача сводится к вычислению T[1, Q];

Тесты

11 6
1 2 8
2 3 1
2 4 7
4 5 12
4 6 2
5 7 10
5 8 1
1 9 100
9 10 8
10 11 1

ответ : 137
---
6 3
1 2 10
1 4 30
2 3 0
4 5 0
4 6 100


ответ : 130
---
6 3
1 2 10
1 4 30
2 3 0
4 5 0
4 6 0

ответ : 40
---

CODE

#include <list>
#include <iostream>

using namespace std;

struct TNode
{
	TNode(short int index, short int name)
	{
		_index = index;
		_name = name;
		left  = NULL;
		right = NULL;
	}

	TNode * left;
	TNode * right;
	short int _name;
	short int _index;
};

TNode * findBranchByIndex(TNode * HEAD,
													short int name)
{
	list<TNode *> front;
	list<TNode *> newFront;
	front.push_back(HEAD);
	TNode * current = NULL;

	while(!front.empty())
	{
		while(!front.empty())
		{
			current = front.front();
			front.pop_front();
			if(current->_name == name)
			{
				return current;
			}
			else
			{
				if(current->right != NULL) newFront.push_back(current->right);
				if(current->left  != NULL) newFront.push_back(current->left);
			}
		}
		front.swap(newFront);
		newFront.clear();
	}
	return HEAD;
}

void addBranch(TNode * father, 
							short int index,
							short int name)
{
	if(father->right == NULL)
	{
		TNode * node = new TNode(index, name);
		father->right = node;
	}
	else
	{
		TNode * node = new TNode(index, name);
		father->left = node;
	}
}

int maxCount(int ** T, int N, int Q, TNode * node)
{
	if (T[node->_index][Q] >= 0 || T[node->_index][Q] < -1 ) return T[node->_index][Q];
	else
	{
		int temp = 0;
		if(!node->left && node->right)
		{ 
			temp = maxCount(T, N, Q - 1, node->right);
			if (temp >= 0)	T[node->_index][Q] = T[node->_index][1] + temp;
			else
			{
				for(int i = Q; i <= N; i++) T[node->_index][i] = -2; 
			}
		}
		else if(node->left  && !node->right)
		{
			temp = maxCount(T, N, Q - 1, node->left);
			if (temp >= 0) T[node->_index][Q] = T[node->_index][1] + temp;
			else
			{
				for(int i = Q; i <= N; i++) T[node->_index][i] = -2;
			}
		}
		else if(!node->left && !node->right) 
		{
			for(int i = Q; i <= N; i++) T[node->_index][i] = -2; 
		}
		else
		{
			int max = 0;
			int current = 0;
			for(int i = 0; i <= Q-1; i++)
			{
				current = T[node->_index][1];
				temp = maxCount(T, N, Q - 1 - i, node->left);
				if( temp >= 0)
				{
					current += temp;
					if(node->right)	temp = maxCount(T, N, i, node->right);
					if(temp >= 0) 
					{
						current += temp;
						if(current > max) max = current;
					}
				}
			}
			if(max >= 0) T[node->_index][Q] = max;
			else
			{
				for(int i = Q; i <= N; i++) T[node->_index][i] = -2;
			}
		}
	}
	return T[node->_index][Q];
}


void print2d(int **T, int N)
{
	
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++) 
		{
			cout.width(3);
			if (T[j][i] >= 0) cout << T[j][i] << " ";
			else if (T[j][i] < -1) cout << "x" << " ";
			else cout << "-" << " ";
		}
		cout << endl;
	}

}

int main()
{
	int N, Q;
	cin >> N >> Q;
	TNode *HEAD = new TNode(0, 1);

	int **T = new int*[N+1];
	for (int i=0; i < N+1; i++)
	{
		T[i] = new int[N+1];
		for (int j = 1; j <= N; j++) T[i][j] = -1;

		T[i][0] = 0;
	}
	T[0][1] = 0;

	int fatherName;
	int name;
	int countOfApples;
	for (int i=1 ; i < N; i++)
	{
		cin >> fatherName >> name >> countOfApples;
		addBranch(findBranchByIndex(HEAD, fatherName), i, name);
		T[i][1] = countOfApples;
	}

	//print2d(T, N);

	cout << maxCount(T, N, Q, HEAD) << endl;

	//print2d(T, N+1);

	cin >> name;
	return 0;
}