CODEWITHSUNDEEP
algorithmdata-structuresgraphdynamic-programmingmaximize
learner-coder
learner-coder

Reputation: 307

Maximum profit earned on weighted un-directed tree

I came across this problem while giving a sample test. The problem was that we have given a tree which is undirected. We can start from any node of our choice. Initially we have power "P" and while going from one node to other node we loose some power "X" (consider as cost of travelling) and earn some profit "Y". So we need to tell that what is the maximum profit that we can earn with a given power ?

Example: First line contains number of nodes and initial power

Next n-1 lines contains node-node-cost-profit

5 4

1 2 1 2

1 3 2 3

1 4 2 4

4 5 2 2

Answer => 7. We can start from 4 and go to 1 and than to 3.

I have applied DFS on this to get maximum profit earned by traversing every single path.

But is there a way to decrease time ??? 

from collections import defaultdict
class tree:
    def __init__(self,nodes):
        self.nodes = nodes
        self.graph = defaultdict(list)
    def add(self,a,b,charge,profit):
        self.graph[a].append([b,charge,profit])
        self.graph[b].append([a,charge,profit])
    def start(self,power):
        maxi = -1
        visited = [False for i in range(self.nodes)]
        for i in range(1,self.nodes+1):
            powers = power
            visited[i-1] = True
            for j in self.graph[i]:
                temp = self.dfs(j,powers,0,visited)
                if temp > maxi:
                    maxi = temp
            visited[i-1] = False
        return maxi

    def dfs(self,node,powers,profit,visited):
        v,p,pro=node[0],node[1],node[2]
        if powers-p < 0:
            return 0
        if powers-p == 0:
            return profit + pro
        profit += pro
        powers = powers-p
        visited[v-1] = True
        tempo = profit
        for k in self.graph[v]:
            if visited[k[0]-1] == False:
                temp = self.dfs(k,powers,tempo,visited)
                if temp > profit:
                    profit = temp
        visited[v-1] = False
        return profit

t = tree(5)
t.add(1,2,1,2)
t.add(1,3,2,3)
t.add(1,4,2,4)
t.add(4,5,2,2)
print(t.start(4))

Upvotes: 2

Views: 384

Answers (1)

Maras
Maras

Reputation: 982

You want to find all paths that have length up to P and take maximum of their profits. You can achieve it in O(n log^2 n) time using centroid decomposition.

Consider all subtrees that you create by deleting a centroid C from the tree. Let's say you have found all paths of length less or equal P and taken a maximum of them (now you'll only consider paths that contain C). Using DFS calculate distance and profit from C to each other node in the tree and store them as pairs in multiset.

For each subtree do:

  1. delete from multiset every pair of values of node from that subtree - O(n log n)

  2. copy all the pairs from the multiset to a list L1 - O(n)

  3. create list L2 of pairs (distance, profit) from the current subtree and sort it by distance in decreasing order - O(n log n)

  4. create variable maxx = 0 and i = 0

  5. for each pair X in L2:

    • while L1[i] <= P - X.distance do: maxx = max(maxx, L1[i].profit), ++i
    • result = max(result, maxx + X.profit)
    • all of it will take at most O(n)

  6. insert all pairs from L2 back to multiset - O(n log n)

Time complexity: O(n log n)

Now you have calculated maximum profit of all paths of length equal or less P in the tree. To get all the values in subtrees run the same algorithm recursively. Since there are at most O(log n) layers using centroid decomposition total complexity is O(n log^2 n).

Upvotes: 2

Related Questions