Двоичная яблоня

[xakkkkker]

Добрый день уважаемые программисты. У меня курсовая и задали такую задачу.

Задача. "Двоичная яблоня".
Яблоня называется двоичной, если в каждой точке ветвления ствол или ветвь разделяется надвое. Точки ветвления, корень и концы веток - это узлы дерева.
Известна масса каждого участка яблони между двумя смежными узлами. Первоначально в яблоне N узлов, а нужно оставить M.
Яблоню можно резать в основаниях ветвей, при этом ветвь и вся часть дерева, растущая выше от разреза, удаляются.
Исходные данные: N, M (1<M<N<100) и список из N-1 тройки. Каждая тройка содержит номера узлов, определяющих участок, и его массу (узлы пронумерованы от 1 до N).
Требуется найти план подрезки дерева, оставляющий наименьшую суммарную массу оставшихся участков.

Например, для исходных данных: N=8, M=3 и набора троек (1,2,19) (2,4,13) (3,2,12) (3,8,17) (3,6,11) и (5,8,10) (8,7,8).
Результат может быть следующим:
Обрезать ветви: (2,4) (3,8) (3,6)

Методы которыми можно выполнить:
1) Ветвей и границ
2) Динамического программирования

Дело вот в чем, я не понимаю эту задачу вообще. А методы Ветвей и границ и Динамического программирования оба я знаю. Подскажите кто нить как ее сделать, хоть алгоритм. :conf used:Хоть нарисуйте это дерево что примерно из себя представляет, Я вообще не могу понять про тройку. Кто нить чем нить помогите.

[malinoff]

Вы себе граф-дерево вообще представляете?
Тройки - это (1_номер_узла_графа,2_номер_узла_гр афа,вес_ребра_между_1_и_2)
1_номер_узла и 2_номер_узла связаны ребром, у которого есть вес.

[xakkkkker]

Что такое граф я некоторое представление имею. malinoff не могли бы вы на пайнте примерно нарисовать это дерево указав тройки. А то я не могу его представить

[xakkkkker]

никто не встречался с подобной задачей?

[malinoff]

http://www.i-u.ru/biblio/archive/ign...p_image008.gif
Если, например, над каждым ребром нарисовать вес, то тройки будут такие:
(цель1,цель1.1,вес_ребра_между_цель 1_и_цель1.1), (цель1,цель1.2,вес_ребра_между_цель 1_и_цель1.2), (цель1.1,цель1.1.1,вес_ребра_между_ цель1.1_и_цель1.1.1) и так далее

[phomm]

http://ru.wikipedia.org/wiki/Двоичное_дерево читай это и все сопутствующие ссылки

[xakkkkker]

Никто не может помочь?