carmelo wrote: > imagine to have a k-ary tree, each node is a room and each edge is a > corridor; each room has a value assigned, you must place cameras in > rooms but if a room has an adiacent room with the camera you can't > place the camera inside...you must place the cameras to have the max > value possibile.. how to choose the rooms?
A level order traversal of the k-ary tree starting from the root (i.e.depth 0) and chosing all the nodes from even numbered depths. So in this case, sum of all the nodes in depth 0, 2, 4 ..., call it x. Another level-order traversal of the k-ary tree starting from depth 1 and chosing all the nodes from odd numbered depths. So in this case, sum of all the nodes in depth 1, 3, 5 ..., call it y. The larger of the 2 values x,y will be your max and it's corresponding nodes will give you the rooms with cameras in them. - GoCooL P.S. I've also responded to your original post on comp.lang.c --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---