Deleting an edge from a tree to minimise the cost-CodePudding

Let's have a tree whose edges are valued by prices, which are some integers. The sum of the prices of all edges we will call the price of the tree. If we cut a tree by deleting one edge, it will break up into two trees. The maximum of their prices we call the cut price. Our task is to find the cheapest cut.

The output should be one number, the minimal price of the cut.

Example:

Input:

First number is the number of vertices. After that we have number of vertices - 1 rows. The first two numbers in the rows are the connections between the vertices, so 1 4 means 1 and 4 are connected. The last number in the row is the 'price' of the edge.

So in this case the output should be 3, because if we delete the edge between 2 and 1 we will get two subtrees, with the edges being 3 and 3 (their price).

(the graph, / and \ are edges, numbers are the vertices, numbers next to the / and \ are the prices of the edges)

I was thinking about this for a while, but don't know the proper algorithm to do this.

The basic program I wrote:

number_of_vertices = int(input())
edges = []
price = []
for i in range(number_of_vertices):
    u, v, c = input().split()
    edges.append([int(u),int(v)])
    price.append(int(c))

I thought about going through every single edge, and deleting them and then calculating, but I don't know how to implement it.

So I made a dictionary of neighbours, and a find_path algorithm to find if there exists an edge between two vertices:

from collections import defaultdict

def find_path(graph, start, end, path=[]):
        path = path   [start]
        if start == end:
            return True
        if start not in graph:
            return False
        for node in graph[start]:
            if node not in path:
                newpath = find_path(graph, node, end, path)
                if newpath: return True
        return False

number_of_vertices = int(input())
edges = []
price = []
for i in range(number_of_vertices - 1):
    u, v, c = input().split()
    edges.append([int(u),int(v)])
    price.append(int(c))
   
graph = defaultdict(set)
for vertices in edges:
    graph[vertices[0]].add(vertices[1])
    graph[vertices[1]].add(vertices[0])
print(find_path(graph, 1, 3)) #this is just to make sure it works      
print(dict(graph)) #this too

CodePudding user response：

First, calculate the total price of the tree, let's say it totalCost. Now we will traverse the tree and try to remove every edge and see if the cut price is minimum or not.

For every Node, we can calculate the price of its child's subtree. If we remove the edge to one child and we know the cost of its subtree then we can easily find the cost of the remaining tree by subtracting the price of the subtree and edge cost that we are removing. let's say we are removing the edge for U to V with cost X and cost of subtree V is costOfSubTree. Then the remaining tree's cost is

costOfRemainingTree = totalCost - costOfSubTree - X

now we have the Cost of two trees after removing the edge from U to V. Now we have the biggest cost(Cut price) and compare it with the minimum Cut we have found so far.

Here Total Cost is 21. The cost of Subtree 2 is 12. Now if we remove Edge from 1-2 we will have two trees. One is Subree 2 with cost 12 and cost of the other tree is (21 - 12 - 4) = 5, here 4 is the edge cost of 1 - 2. Now we have two trees with cost 5 and 12, So here the Cut Cost is 12.

In this manner, we can try every edge and try to minimize the answer. And if we know which edge to remove we can easily find the nodes of two trees.

CodePudding user response：

LOOP over nodes
  Calculate cost of subtree from node
LOOP over links
  Calculate cut cost of link max( subtree cost of deepest node, tree cost - subtree cost - link cost )
  If cut cost less than previous cheapest, replace cheapest
Output cheapest found