24 aprile 2024 - esercizio 1

[CuriousCI]

[Traster-uni]

Questa è la mia soluzione, a mio parere fin troppo semplicistica, al solito commenti e alternative sono benvenuti.

[Elia-Belli]

Update MST

Siccome $(u,v)$ non è stato inizialmente scelto per l'inserimento in $T$ vuol dire che avrebbe introdotto un ciclo: analizzando gli archi di tale ciclo possiamo valutare quale di questi sia il più pesante e sostituirlo con $(u,v)$ in modo da ridurre il peso, se non è lui stesso.

def update_MST(T,u,v,new_w):
    P = BFS(T,u) #vettore dei padri da u in T
   
    max = new_w  #peso dell'arco (s,t) di peso maggiore nel ciclo
    s = u
    t = v
    z = v
    while(P[z] != z):
        if(w(z,P[z]) > max):
            max = w(z,P[z])
            s = z
            t = P[z]
        z = P[z]
    
    if(max != new_w):
        T.remove((s,t))
        T.add((u,v))

[CarloDaRomadev]