samedi 13 novembre 2021

Random change in weight of an edge in a spanning tree in Python

The task is as follows: I build a graph and in it I need to select 5 edges at random and change their weight. The delta value of the weight change is 3. Then you need to find the remaining tree with the minimum weight, but I have already written this in the code. Please tell me how to make the first condition.

Here is my code:

N, M = map(int, input().split())
Edges = []
for i in range(M):
    start, end, weight = map(int, input().split())
    Edges.append([weight, start-1, end-1,i+1])
Edges.sort()
Comp = [i for i in range(N)]
Ans_len = 0
Ans = []
for weight, start, end, num in Edges:
    if Comp[start] != Comp[end]:
        Ans_len += weight
        Ans.append(num)
        a = Comp[start]
        b = Comp[end]
        for i in range(N):
            if Comp[i] == b:
                Comp[i] = a
        if len(Ans) != N-1:
            print(-1)
        else:
            print(Ans_len)
            print("".join(map(str,Ans)))

Undirected weighted graph without multiple edges with N vertices and M edges




Aucun commentaire:

Enregistrer un commentaire