How to minimize the sum of all nodes in a tree?

Правка en1, от I_love_Saundarya, 2019-12-08 10:46:51

Given a tree with 'n' nodes and 'n-1' edges.

We are also given a set of 'n-1' weights .

We have to assign each weight to exactly one of the edges.

We have to assign it in a way such that the sum of all nodes in a tree is minimized.

Value of a node = maximum weight of all of its adjacent edges.

Example:- Edges:- (1--2), (2--3)

Weights:-{1,2}

Solution : — Assigning weight '2' to edge '1--2' and weight '1' to edge '2--3' , we get,

value of node '1' : — 2

value of node '2' : — 2

value of node '3' : — 1

Total minimum sum possible : — (2+2+1)=5 .

How to approach ?

Теги #trees

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский I_love_Saundarya 2019-12-08 10:46:51 677 Initial revision (published)