How to write a function that returns the sum of the weights of a spanning tree?

  algorithm, python, tensorflow

Fake minimum height tree
Given a graph, the minimum length tree refers to the tree with the smallest sum of weights among the trees connecting all vertices.

Ellis, who was learning about the minimum height tree thought it wasn’t fun to choose only vertices that were too small. So, Ellis thought, he wants to find a tree that has the smallest sum of weights among the trees that connect all the vertices, whose weights are all greater than or equal to cc. That is, an edge whose weight is less than cc must not exist in the tree. Let’s call this a peculiar spanning tree.

Help Ellis write a program to find an unusual spanning tree.

If there is no spanning-tree whose weights are all greater than or equal to cc, print -1.

Input

The first line is given a constant cc that determines the number of vertices, the number of edges, and the weights of the edges of the unusual spanning tree.

From the second line, information on the edge is given. Each line is made up of integers a b c, which means that there is an edge with weight c between a and b.

Print

Outputs the sum of the weights of the edges of the minimum spanning tree.

Input example

8 11 2
0 1 3
0 5 1
1 2 1
1 3 4
1 5 3
2 4 2
2 7 4
2 6 1
3 4 3
4 6 4
6 7 2

Copy

Example output

21
import sys
sys.setrecursionlimit(100000)

def getPseudoMST(graph, c) :
    '''
    Given a graph, write a function that returns the sum of the 
weights of the spanning tree whose weight 
is the smallest among spanning trees whose edge weight is greater than or equal to c.
    '''

    return 0

def main():
    '''
    Do not change this code
    '''

    line = [int(x) for x in input().split()]

    n = line[0]
    m = line[1]
    c = line[2]

    graph = [ [] for i in range(n) ]

    for i in range(m) :
        line = [int(x) for x in input().split()]

        graph[line[0]].append((line[1], line[2]))
        graph[line[1]].append((line[0], line[2]))

    print(getPseudoMST(graph, c))

if __name__ == "__main__":
    main()

Source: Python Questions

LEAVE A COMMENT