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